哈希&双指针问题-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