哈希表刷题总结

1. 删除有序数组中的重复项

   题目描述：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解题思路：开始记录数组开始的第一个元素值，使用一个变量i不停去遍历数组，直到当前遍历的值与记录的值不一样时，则把该元素值插入到头部的头部，插入的位置则是由另一个变量j来记录确定。最后j的值便是数组中不重复元素的长度，返回j+1即可完成题目要求。（因为j是从0开始的，所以返回的值应该是j+1）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i=1,j=0;
        int temp=nums[0];
        while(i<nums.size())
        {
            if(nums[i]!=temp)
            {
                nums[++j]=nums[i];
                temp=nums[i];
            }
            i++;
        }
       
        return j+1;
    }
};
           

该方法的时间复杂度为O（n），空间复杂度为O（1），实现了题目要就的“就地”。

思路一的代码改进

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        int j=0;
       for(int i=0;i<n;i++)
       {
           if(nums[i]!=nums[j])
               {
                    nums[++j]=nums[i];
                    
               }
            
       }
       return j+1;
    }
           

官方提供的代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        int j=0;
       for(int i=0;i<n;i++)
       {
           if(i==0||nums[i]!=nums[i-1])
               {
                    nums[j]=nums[i];
                    j++;
                    
               }
            
       }
       return j;
    }
};
           

1. 两数之和

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

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

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

解题思路一：该思路比较直接，也比较笨拙。没遍历一个元素时，便记录该值与目标值的差，接下来便在该值后面的所有元素中寻找是否存在该元素（为什么只需要遍历该元素的后面元素，是因为当遍历到该元素时，已经说明该元素与前面的元素相加的值不等于目标值），若存在，返回两个元素的下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> find;
        for(int i=0;i<nums.size();i++)
        {  
            int temp=target-nums[i];
            for(int j=i+1;j<nums.size();j++)
            {
                
               
                    if(nums[j]==temp)
                    {  return{i,j};
                    }
                  
                
            }
           
        }
        return {};
    }
};
           

官方解法：构建一个映射表来存放数据元素以及索引值，其中key是数组中的元素值，value是数组中的元素索引。接下来遍历整个数组,将每个数组元素与目标值求差，将差值拿到映射表中去查找，如果存在该key值，则直接返回当前元素的位置以及该key值对应的value值，否则将该元素当组key值，元素在数组中的位置当做value插入映射表中。如果不存在满足要求的元素，则返回空值。

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

15.三数之和

题目描述：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路：数组里面有两类障碍，一类是数组重复，若不消除重复元素很可能导致相同结果重复输出；另一类是元素无序，如果有序的话，那么可以根据当前三值之和来判断正确的元素寻找方向。所以，在开始的时候首先对输入数组进行排序，然后开始遍历排序后的数组，如果当前元素值和上一个元素值相等则直接跳过（导致重复输出），接下来去当前元素的右方去找符合要求的元素（为什么是右方尼？其实跟第二天的题解中原理相同，如果再去查找左方元素会导致进行重复的过程，毫无意义。）当右方边界上的两个元素的值与当前遍历的值得元素和等于0，则这三个元素正式我们要找的正确输出信息，此时需要注意，当前正在遍历的元素不止与这一对元素的和为0，再往里面找很可能还有满足要求的元素，所以不能停止遍历，但同时我们还是需要去消除重复元素的干扰，继续向里面进行遍历，如果三值元素和大于0，则说明右边的元素大了，该缩小右域的边界，同理，若小于0，则应缩小左域的边界，最后将满足要求的所有元素输出。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        
        sort(nums.begin(),nums.end());
        if(nums[0]>0) return result;
        for(int i=0;i<nums.size();i++)
        {
            if(i>0&&nums[i]==nums[i-1])
                continue;
            int left=i+1;
            int right=nums.size()-1;
            while(left<right)
            {
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0)
                {
                   result.push_back({nums[i],nums[left],nums[right]});
                while(left<right&&nums[right]==nums[right-1]) right--;
                while(left<right&&nums[left]==nums[left+1]) left++;
                right--;
                left++;
                }
                else if(sum>0) right--;
                else left++;
            }
        }
        return result;
    }
};
           

18.四数之和

题目描述：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

思路：整体思路与三数之和相同，只不过三数之和中我们固定一个值i，用双指针left和right去找其他两个满足条件的数，而在四数之和中骂我们可以固定两个值i和j，然后再用双指针法去找其他两个值，使得四值加起来的值等于target。思路很简单，但值得注意的是，在三指针中，因为提前给数组排过序，我们判断如何数组最小值大于target时，该输入值便没有满足题目要求的项，那是因为三值之和中target为0，如果数组第一个值比0大，那么后面的所有值也都比0大，比0大的数再加任何一个比0大的数都不可能变小，而在本题中target可真可负，如果仅用数组最小值大于target来减枝的话，在一个例子中，target=-5，数组为[-4，-1,0,0]，此时会发生错误。所以在判断数组最小值大于target时，需得target大于0才行。具体的实现代码如下所示，更细节的减枝和去重都标注在代码中。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        if (nums[0]>0&&nums[0]>target) return result;
        for(int i=0;i<nums.size();i++)
        {   if(i!=0&&nums[i]==nums[i-1]) continue;//去重，与三值和原理相同
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]>target&&target>0) break;
                //target为正时，两个值之和都大于target，且nums[j]一定是大于0的，所有
                //后续的数也一定是大于0的，所以肯定找不到符合题意的集。
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                long temp=(long)target-nums[i]-nums[j];
                int l=j+1;
                int r=nums.size()-1;
                while(l<r)
                {
                if(nums[l]+nums[r]>temp) r--;
                else if(nums[l]+nums[r]<temp) l++;
                else
                {
                    result.push_back( {nums[i],nums[j],nums[l],nums[r]});

                    while(l<r&&nums[r-1]==nums[r]) r--;
                    while(l<r&&nums[l+1]==nums[l]) l++;
                    r--;
                    l++;
                }

                } 
                 
            }
        }
        return result;
    }
};
           

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词

思路：题目的要求就是统计两个字符串中的字符数，判断s有的t也要有，且有的个数相同，且所有的字符都是小写的，那么久好说了，我们只需要设置一个大小为26的数组统计s字符每一位出现的次数，再次统计t时，将字符出现的次数相抵消，如果最后数组中还存在非0的项，那么就说明不符合题意。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26]={0};
        for(int i=0;i<s.size();i++)
        {
            record[s[i]-'a']++;
        }
        for(int j=0;j<t.size();j++ )
        {
            record[t[j]-'a']--;
        }
        for(int k=0;k<26;k++)
        {
            if(record[k]!=0)  return false;
        }
        return true;
    }
};
           

注释：当题目输入大小受限时，可以用数组替代哈希表。

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路：求两个数组的交集，并要去重，去重在一个无序的数组中很麻烦，且输出不需要有序，所以我们用到了unordered_set，它对元素不会进行排序，节省了很多时间。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
        unordered_set<int>  result;
        unordered_set<int> nums1_set(nums1.begin(),nums1.end());
    
        for(int i=0;i<nums2.size();i++)
        {
            if(nums1_set.find(nums2[i])!=nums1_set.end())
                result.insert(nums2[i]);
        }
        return vector<int>(result.begin(),result.end());
    }
};
           

454四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

思路：题目的大意是四个长度都为n的的数组，能否在每个数组中找到一个元素，致使四个元素加起来的和等于0，若存在，有多少个元素组满足这个要求。也就是说，题目要求输出个数，且不需要去重（元素相同但下标不同依然是两个不同的元组）。既然只要求返回个数，那我们就可以把前两个数组的每组元素和放入map中（由于不用去重，所以map的value部分存储的是和为key值元组的个数），接下来，我们去便利另外两个数组，把他们的相反值拿到map中去查找，若找到，则统计变量则加上以该值为key的value值。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        
        int count=0;
        map<int,int> IntMap;
        for(int i=0;i<nums1.size();i++)
        {
            for(int j=0;j<nums2.size();j++)
            {
                IntMap[nums1[i]+nums2[j]]++;//注意不用去重
            }
        }
        for(int i=0;i<nums3.size();i++)
        {
            for(int j=0;j<nums4.size();j++)
            {
                if(IntMap.find(0-(nums3[i]+nums4[j]))!=IntMap.end())
                    count+=IntMap[0-(nums3[i]+nums4[j])];//注意不用去重
            }
        }
        return count;
    }
};
           

202.快乐数

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

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：本题的结题关键正如题目所说，当一个数的各位的平方相加和出现循环时，就肯定不是快乐数

class Solution {
public:
    bool isHappy(int n) {
      
      unordered_set<int> Iset;
      while(1)
      {   int sum=0;
          while(n)
          {
              
              sum+=pow(n%10,2);
              n /=10;
              
          }
          if(sum==1) return true;
          if(Iset.find(sum)!=Iset.end())
                return false;
            else Iset.insert(sum);
             n=sum;
      }
           

    }
};
           

383 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26]={0};
        for(int i=0;i<magazine.size();i++)
        {
            record[magazine[i]-'a']++;
        }
        for(int i=0;i<ransomNote.size();i++)
        {
            record[ransomNote[i]-'a']--;
        }
        for(int i=0;i<26;i++)
        {
            if(record[i]<0)
            return false;
        }
        return true;
    }
};
           

总结：二数之和和二值相加只需要将前面遍历过的值保存下来，后面遍历新值时只需要去找保存的元素里有没有对应差值的。而三值相加和四值相加属于同一类问题，三值之和和四值之和要注意去重和减枝问题。在三值相加中，由于数组是经过排序的，所以在最外层的元素遇到与前值相等时应跳过避免去重，同理，当找到第二个和第三个值时，也需要进行去重；四值相加时，尤其注意找第一个值和第二个值时（第一层和第二层循环）的去重和减枝条件。