哈希&双指针问题-LeetCode 128、18（哈希set查询，二分查找）
哈希&双指针问题-LeetCode 128、18（哈希set查询，二分查找）
作者：TeddyZhang，公众号：算法工程师之路
DFS基础问题：LeetCode #128 #18
1
编程题
【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