哈希表刷題總結

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;
    }
};
           

總結：二數之和和二值相加隻需要将前面周遊過的值儲存下來，後面周遊新值時隻需要去找儲存的元素裡有沒有對應內插補點的。而三值相加和四值相加屬于同一類問題，三值之和和四值之和要注意去重和減枝問題。在三值相加中，由于數組是經過排序的，是以在最外層的元素遇到與前值相等時應跳過避免去重，同理，當找到第二個和第三個值時，也需要進行去重；四值相加時，尤其注意找第一個值和第二個值時（第一層和第二層循環）的去重和減枝條件。