【LeetCode】N数和

1. 3Sum

给定一个无序数组（可能存在重复元素），是否存在三个数之和为0，输出所有不重复的三元组。

e.g. 给定数组 [-1, 0, 1, 2, -1, -4]，

结果集为：
[
　　[-1, 0, 1],
　　[-1, -1, 2]
]

原理：

首先升序排序

----------------------------------------------------
^  ^                                               ^
|  |                                               |
|  j                                               k
i

j 往后扫，k 往前扫

三数和 < 0 就 j++，> 0 就 k--

直到 == 0 再取下一组

C++实现：

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        // 控制i不重复，只指向一组重复数字的第一个
        if (i > 0 && nums[i] == nums[i-1])
            continue;
        int j = i + 1, k = nums.size() - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else if (nums[i] + nums[j] + nums[k] > 0) {
                k--;
            } else {
                result.push_back({nums[i], nums[j], nums[k]});
                // 控制j不重复，只指向一组重复数字的第一个
                while (j < k && nums[j] == nums[j+1])
                    j++;
                // 控制k不重复，只指向一组重复数字的最后一个
                while (j < k && nums[k] == nums[k-1])
                    k--;
                j++;
                k--;
            }
        }
    }
    return result;
}    

第4行如果写 i < nums.size() - 2会报 Runtime Error 错，不知道为什么？

2. 3Sum Closest

给定一个无序数组（可能存在重复元素），是否存在三个数之和最接近给定数target，输出这三个数的和。（假设每条输入只有唯一答案）

e.g. 给定数组 [-1, 2, 1, -4]，target = 1

则最接近target的和为2 （-1 + 2 + 1 = 2）

C++实现：

int threeSumClosest(vector<int>& nums, int target) {
    // 数组元素小于等于3个则直接返回数组和
    if (nums.size() <= 3) {
        return accumulate(nums.begin(), nums.end(), 0);
    }
    int close = nums[0] + nums[1] + nums[2];
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i-1])
            continue;
        int j = i + 1, k = nums.size() - 1;
        while (j < k) {
            int current = nums[i] + nums[j] + nums[k];
            if (abs(current - target) < abs(close - target)) {
                close = current;
                if (current == target) {
                    return current;
                }
            }
            (current < target) ? j++ : k--;
        }
    }
    return close;
}

PS：

C++对应的Java代码

vector<vector<int>>                                            List<List<Integer>>
sort(nums.begin(), nums.end());                                Arrays.sort(nums)；
result.push_back({nums[i], nums[j], nums[k]});                 result.add(Arrays.asList(nums[i], nums[j], nums[k]));
abs(n)                                                         Math.abs(n)

3. 4Sum

给定一个无序数组（可能存在重复元素），是否存在四个数之和为目标数target，输出所有不重复的四元组。

e.g. 给定数组[1, 0, -1, 0, -2, 2]，target = 0.

结果集为：
[
　　[-1, 0, 0, 1],
　　[-2, -1, 1, 2],
　　[-2, 0, 0, 2]
]

原理与 3 Sum 相似，首先升序排序，i 从第一个扫到最后，j 从 i + 1 扫到最后。

两个指针为 p 和 k ，p 往后扫，k 往前扫，四数和 < 0 就 p++，> 0 就 k--；直到 == 0 再取下一组 p 和 k。

C++实现：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int n = nums.size();
    if (n < 4)    return {};
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1])    continue;
        // 提高效率，本轮能取的最小的和与本轮能取的最大的和
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)   break;
        if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target)   continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1])    continue;
            // 提高效率，本轮能取的最小的和与本轮能取的最大的和
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
            if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
            // 最后两个指针p和k在最内层while上面定义
            // 如模仿三数和在上面定义k并在j循环体内控制条件写j < k会导致j扫不到最后
            int p = j + 1, k = n - 1;
            while (p < k) {
                if (nums[i] + nums[j] + nums[p] + nums[k] < target)  p++;
                else if (nums[i] + nums[j] + nums[p] + nums[k] > target)  k--;
                else {
                    result.push_back({nums[i], nums[j], nums[p], nums[k]});
                    while (p < k && nums[p] == nums[p + 1]) p++;
                    while (p < k && nums[k] == nums[k - 1]) k--;
                    p++;
                    k--;
                }
            }
        }
    }
    return result;
}