哈希表相关题目-leetcode简单

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

不能使用双指针方法，因为数组是无序的；虽然可以对数组排序，但是排序后的数组索引位置改变，而本题需要返回索引位置。

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         vector<int> res;
 5         sort(nums.begin(), nums.end()); //排序后索引位置就变了
 6         int f=0,b=nums.size()-1;
 7         while(f<b){
 8             if(nums[f]+nums[b]==target){
 9                 return vector<int>{f,b};
10             }else if(nums[f]+nums[b]>target){
11                 b--;
12             }else{
13                 f++;
14             }
15         }
16         return res;
17     }
18 };

错误的双指针方法

方法一、暴力方法

遍历每个元素 $相等的目标元素。时间复杂度：O(n^2)。$

两遍哈希表

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i]本身！时间复杂度：

 1 //[3,3] 时不通过
 2 class Solution {
 3 public:
 4     vector<int> twoSum(vector<int>& nums, int target) {
 5         //vector<int> res;
 6         map<int,int> maps;
 7         int n=nums.size();
 8         for(int i=0;i<n;i++){
 9             maps.insert(make_pair(nums[i],i));   //maps.insert(make_pair<int,int>(nums[i],i)); // not ok    
10             //maps[nums[i]]=i;  //ok
11         }
12         for(int i=0;i<n-1;i++){  //此处是n-1
13             int tar = target-nums[i];
14             if(maps.find(tar)!=maps.end() && maps[tar]!=i)
15                 //return vector<int>(i,maps[tar]); //错误写法
16                 //return {i,maps[tar]}; //ok
17                 return vector<int>{i,maps[tar]}; 
18         }
19         return {};
20     }
21 };
22 
23 //make_pair 后买你不需要加类型
24 //注意区分map与unorder_map

错误的实现

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         int sz = nums.size();
 5         vector<int> res;
 6         if(sz<2)
 7             return res;
 8         
 9         map<int,int> m;
10         for(int i=0;i<sz;i++){
11             m[nums[i]]=i;
12         }
13         
14         for(int i=0;i<sz-1;i++){
15             if(m.find(target-nums[i]) != m.end() && m[target-nums[i]]!=i){
16                 res.push_back(i);
17                 res.push_back(m[target-nums[i]]);
18                 break;
19             }      
20         }
21         return res;
22     }
23 };

实现1

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         unordered_map<int, int> m;
 5         for (int i = 0; i < nums.size(); ++i) {
 6             if (m.count(target - nums[i])) {
 7                 return {i, m[target - nums[i]]};
 8             }
 9             m[nums[i]] = i;
10         }
11         return {};
12     }
13 };

实现2

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

使用异或的方法

 1 class Solution {
 2 public:
 3     int singleNumber(vector<int>& nums) {
 4         int res=0;
 5         for(int i=0;i<nums.size();i++){
 6             res = res^nums[i];     
 7         }
 8         return res;
 9     }
10 };

异或

哈希算法

若第一次出现，插入哈希集
第二次出现，冲哈希集内删除
最后剩下的就是那个只出现一次的数字

 1 class Solution {
 2 public:
 3     int singleNumber(vector<int>& nums) {
 4         unordered_set<int> s;
 5         for(int i=0;i<nums.size();i++){
 6             if(s.count(nums[i]))
 7                 s.erase(nums[i]);
 8             else
 9                 s.insert(nums[i]);
10             
11         }
12         int res;
13         for(auto i : s)
14             res = i;
15         
16         return res;
17     }
18 };

集合

202. 快乐数

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

输入: 19
输出: true
解释: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

；