哈希&雙指針問題-LeetCode 128、18（哈希set查詢，二分查找）

2019 年 10 月 7 日
筆記

作者：TeddyZhang，公眾號：算法工程師之路

DFS基礎問題：LeetCode #128 #18

編程題

【LeetCode #128】最長連續序列 給定一個未排序的整數數組，找出最長連續序列的長度。

要求算法的時間複雜度為 O(n)。

示例:

輸入: [100, 4, 200, 1, 3, 2] 輸出: 4 解釋: 最長連續序列是 [1, 2, 3, 4]。它的長度為 4。

解題思路： 首先使用一個哈希set將我們的數據全都保存，然後遍歷整個數組，假如遍歷到了數字A，其一定在哈希set中，這是毋庸置疑的。接着我們需要進入一個while循環去判斷A+1，A+2，A+3…是不是也在這個哈希表中，如果嘗試到數字B，其不在哈希表中則退出，此時最長連續序列B-A。

既然我們查找過了A+1，A+2，A+3, 其在哈希表中，那麼我們遍曆數組的時候要需要遍歷這些值么？顯然不需要，因此我們可以優化一下，什麼時候才需要進入上述過程！

當某一個數的前一個數沒有在數組，也就是沒有在哈希set中，我們就從這個數字開始遍歷，統計到的連續序列一定是該部分最長的！！！

C++代碼：

class Solution {  public:      int longestConsecutive(vector<int>& nums) {          if(nums.size() == )  return ;          unordered_set<int> mySet(nums.begin(), nums.end());          int res = ;            for(auto num: nums){              if(mySet.count(num - ) == ){                  int tmp = num;  //保存初始數據                  while(mySet.count(tmp)){                      tmp++;                  }                   res = max(res, tmp-num);              }          }          return res;      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/longest-consecutive-sequence

【LeetCode #18】四數之和

給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。

注意：答案中不可以包含重複的四元組。

示例：

給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

滿足要求的四元組集合為： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路： 四數之和的大體思路是：首先固定兩個數，然後將思路之和的問題變成兩數之和，使用雙指針的方法去尋找，由於對於兩數之和，使用雙指針的前提數組是一個排序數組，因此我們先對該數組進行排序，然後根據上述的思路再去遍歷。

注意在遍歷時候的幾種剪枝方法：

如果nums[i]>target && target>0，說明後面的nums[i]肯定不存在我們想要的值，因為後面的值都大於target.
固定的兩個元素不能是相同元素，如果是相同的元素，那麼經過兩數求和算法後勢必會存在重複的四元組，因此我們需要判斷j > i+1 && nums[j][j-1], 如果為真，兩數之和算法不會運行！
兩數求和怎麼去重的就不解釋了，遇到重複的，讓指針跳過就好了！
如果不想這麼麻煩，可以使用DFS方法中的set去重

C++代碼

class Solution {  public:      vector<vector<int>> fourSum(vector<int>& nums, int target) {          if(nums.size()<) return {};          sort(nums.begin(),nums.end());          vector<vector<int>> res;          for(int i=;i<nums.size()-3;i++)          {              if(nums[i]>target&&target>) break;              if(i> && nums[i]==nums[i-1])                  continue;    // 去重              for(int j=i+;j<nums.size()-2;j++)              {                  if(j>i+ && nums[j]==nums[j-1])                      continue;  // 去重                  int l=j+;                  int r=nums.size()-1;                  while(l<r)                  {                      if(nums[i]+nums[j]+nums[l]+nums[r]<target)                          while(l<r && nums[l]==nums[++l]);  // 去重                      else if(nums[i]+nums[j]+nums[l]+nums[r]>target)                          while(l<r && nums[r]==nums[--r]);                      else                      {                          vector<int> temp{nums[i],nums[j],nums[l],nums[r]};                          res.push_back(temp);                          while(l<r && nums[l]==nums[++l]);                          while(l<r && nums[r]==nums[--r]);                      }                  }              }          }          return res;      }  };

附一個自己寫的DFS超時代碼，哈哈哈，關鍵不是DFS，這個不難，主要是去重比較複雜，我這裡使用的是set去重，不管怎麼樣，都會超時。。。

class Solution {  public:      set<vector<int>> res;      vector<vector<int>> res_;      vector<int> tmp;      vector<vector<int>> fourSum(vector<int>& nums, int target) {          if (nums.empty())  return res_;            dfs(res, nums, target, );          for(auto i: res){              res_.push_back(i);          }          return res_;      }        void dfs(set<vector<int>>& res, vector<int>& nums, int target, int start){          if (tmp.size() > ){              return;          }          if(tmp.size() == ){              vector<int> t;              for(auto i: tmp){                  t.push_back(i);              }   // set數組對於不同順序的相同元素認定為不同元素，無法去重，因此先排序              sort(t.begin(), t.end());              if(target ==   && res.count(t) == ){                  res.insert(t);              }              return;          }          for(int i = start; i < nums.size(); i++){              if(i != start && nums[i] == nums[i-1]){                  continue;              }              tmp.push_back(nums[i]);              dfs(res, nums, target-nums[i], i+);              tmp.pop_back();          }      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/4sum