【算法-哈希表5】看似哈希，实则双指针。

今天，带来哈希表和双指针相关算法的讲解。文中不足错漏之处望请斧正！

理论基础点这里

---

四数之和

题意简化

四数之和，去重版：找不重复的四元组

• 四元组四个元素下标不同, 和为target
• 四元组不重复
  • 由于输出四元组的顺序没有限制, 所以四元组之间, 元素的值必须完全不同
    • 一个四元组中的元素能以任意顺序构成另一个四元组, 就称两个四元组是重复的
    • 只对a/b/c/d的某一个去重, 还会遇到重复的四元组

题意转化

在数组nums中收集所有满足条件的四元组（不能重复），四元组条件：

• 四个元素下标不同
• 四元素和为target

解决思路(抽象)

根据《三数之和》，我们还是选择用双指针的方法来做。
循环不断拿取四元组, 满足条件就收割(不能收割重复的结果)。

怎么拿数

怎么拿数能最快拿到结果(避免暴力遍历全部组合)？

排序，根据有序性动态控制双指针, 控制四数之和的大小, 保证自己逐渐接近结果, 而不是死板地暴力遍历所有可能性。

• 两层循环静态拿数, 两个指针动态拿数
  • 静态拿数：i++, j++
  • 动态拿数：双指针根据四数之和与target的大小移动

怎么去重

对a/b/c/d都要去重。

对ab的去重: ab是每次固定拿取的元素, 从这里去重, 是静态去重。
解释：假如本轮的a/b和上一轮的a/b相同, 并且上一轮的a和b可以和后面的某两个元素cd组成结果集, 那么我这一轮的ab也会找到上一轮已经组合过的cd再次组合, 成为重复的结果集

对cd的去重：cd是每次动态拿取的元素, 从这里去重, 是动态去重
解释：[0, -1, -1, -1, 1, 1, 1]，这个例子只有一个结果集：[0, -1, 0]当我们收获了第一个结果集[0, -1, 1]后，left和right按理讲都往里面收缩一下。但不一定只是一下，如果只收缩一下，那就可能会重复收割相同的结果集。

编程实现(具体)

剪枝有细节。

剪枝

有些朋友可能会延续三数之和的思路，直接这样剪枝：

if(nums[i] > target) break;
1

但这样其实是默认了a、b、c、d都是正数。本题会有这样的情况：

nums = [-4, -1, 0, 0]
target = -5
1
2

再看看，[-4, -1, 0, 0]明明是符合条件的结果集，但是nums[i](-4) > target(-5)，直接break了。

所以，我们只有nums[i]和target都为正数才能剪枝。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;

        // 排序
        sort(nums.begin(), nums.end());

        // 取固定的ab, 取动态变化的cd, 收割结果集
        for (int i = 0; i < nums.size(); ++i) { // 固定取a
            // 对a剪枝: 本题有负数, 只有二者都为正数才能这样剪枝
            if (nums[i] > 0 && target > 0 && nums[i] > target) break; 
            if (i > 0 && nums[i] == nums[i - 1]) continue; // a的去重

            for (int j = i + 1; j < nums.size(); ++j) { // 固定取b
                // 对ab的和剪枝:
                if (nums[i] + nums[j] > 0 && target > 0 && nums[i] + nums[j] > target) break;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // b的去重
                
                int left = j + 1; // 移动取c d
                int right = nums.size() - 1;
                while (left < right) { // left 和 right 移动取 cd , 收割结果集
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; // long long 防止相加溢出
                    if (sum > target) --right; // 四数之和大于target, 某个数需要变小, 让right--
                    else if (sum < target) ++left; // 四数之和小于target, 某个数需要变大, 让left++
                    else { // 收割结果集, 并跳过相同结果集(去重)
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});

                        while (left < right && nums[left] == nums[left + 1]) ++left; // c的去重
                        while (left < right && nums[right] == nums[left - 1]) --right; // d的去重

                        // left 和 right 迭代, 继续移动, 收割结果集
                        ++left;
                        --right;                        
                    }
                }
            }
        }

        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

步骤概括：

• 排序
• fori静态取a
  • 对a剪枝
  • 对a去重, 跳过已经收割过的结果集
  • forj静态取b
    • 对a+b剪枝
    • 对b去重, 跳过已经收割过的结果集
    • left和right动态取cd
      • 四数之和小于target, 某个数需要变大, 让left++
      • 四数之和大于target, 某个数需要变小, 让right–
      • 四数之和等于target, 收割结果
        • 对cd去重
          • 因为本身就在移动找结果集, 所以取到结果后才能开始去重
        • left 和 right 迭代, 继续移动, 收割结果集
• 返回结果集

---

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！