数据结构之 哈希表习题 力扣oj(附加思路版)

哈希表用法

哈希表：键 值对

键：可以看成数组下标，但是哈希表中的建可以是任意类型的，建不能重复,可以不是连续的

值：可以看成数组中的元素，值可以重复，也可以是任意类型的数据

#include
#include //无序哈希，
//在哈希表中不一定按照你输入的顺序存储的，是随机存储的但是每次输出的顺序不随机都是一致的
#include  //有序哈希：默认按照键从小到大存储
 
using namespace std;
 
int main()
{
	unordered_map<int, int> u_map;
    
	u_map[9]++; //可以使用这种方式计数
 
	//find() ,find函数的返回值是迭代器，参数是key,
	//如果哈希表中存在键值为key的键值对，返回指向这个键值对的迭代器，否则返回和end()一样的迭代器
 
	if (u_map.find(79) != u_map.end())
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}
	return 0;
}

---

两数之和 

1. 两数之和https://leetcode.cn/problems/two-sum/

        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

        你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

        你可以按任意顺序返回答案。

首先创建一个哈希表，利用哈希表的性质键值对解决本题目。利用find函数寻找数组中元素1与target-数组中元素2是否有相等的值。如果相等返回哈希表的键值。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       map<int,int>m;
       for(int i=0;isize();i++)
       {
            if(m.find(target-nums[i])!=m.end())
                return {m[target-nums[i]],i};
            else
                m[nums[i]]=i;
       }
       return {};
    }
};

重复元素 

217. 存在重复元素https://leetcode.cn/problems/contains-duplicate/

        给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

利用哈希表[ ]计数 

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int,int>m;
        for(int i=0;isize();i++)
        {
            m[nums[i]]++;
            if(m[nums[i]]>=2)
                return true;
        }
        return false;
    }
};

219. 存在重复元素 IIhttps://leetcode.cn/problems/contains-duplicate-ii/

        给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int,int>m;
       for(int i=0;isize();i++)
       {
        if(m.find(nums[i])!=m.end() && i-m[nums[i]]<=k)
            return true;
        else
         m[nums[i]]=i;
       }
       return false;
    }
};