15.三数之和

[rocksc30]

Rock 2023-1-3

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            List<List<Integer>> list = twoSum(nums, -nums[i], i+1);
            for (List<Integer> tuple : list) {
                tuple.add(nums[i]);
                ans.add(tuple);
            }
            while (i < nums.length - 1 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return ans;
    }

    public List<List<Integer>> twoSum(int[] nums, int target, int start){
        // 排序 + 双指针
        Arrays.sort(nums);
        int left = start, right = nums.length - 1;
        List<List<Integer>> ans = new ArrayList<>();

        while(left < right){
            int sum = nums[left] + nums[right];
            int leftNum = nums[left], rightNum = nums[right];
            if (sum > target){
                while (right > left && nums[right] == rightNum){
                    right--;
                }
            } else if (sum < target){
                while (left < right && nums[left] == leftNum){
                    left++;
                }
            } else {
                List<Integer> one = new ArrayList<>();
                one.add(nums[left]);
                one.add(nums[right]);
                ans.add(one);
                right--;
                left++;
                while (right > left && nums[right] == rightNum){
                    right--;
                }
                while (left < right && nums[left] == leftNum){
                    left++;
                }
            }
        }
        return ans;
    }
}

[rocksc30]

时间复杂度不难算，排序的复杂度为 O(NlogN)，twoSumTarget 函数中的双指针操作为 O(N)，threeSumTarget 函数在 for 循环中调用 twoSumTarget 所以总的时间复杂度就是 O(NlogN + N^2) = O(N^2)。

[Ni-Guvara]

先排序再去重然后后用双指针

[rocksc30]

先排序再去重然后后用双指针

每次循环都需要去重

[rocksc30]

nSum问题:

/* 注意：调用这个函数之前一定要先给 nums 排序 */
// n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
vector<vector<int>> nSumTarget(
    vector<int>& nums, int n, int start, long target) {

    int sz = nums.size();
    vector<vector<int>> res;
    // 至少是 2Sum，且数组大小不应该小于 n
    if (n < 2 || sz < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 双指针那一套操作
        int lo = start, hi = sz - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {
        // n > 2 时，递归计算 (n-1)Sum 的结果
        for (int i = start; i < sz; i++) {
            vector<vector<int>> 
                sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}

n == 2 时是 twoSum 的双指针解法，n > 2 时就是穷举第一个数字，然后递归调用计算 (n-1)Sum，组装答案。
本函数的时间复杂度应该是 O(N^(n-1))

[Ni-Guvara]

leetcode 里面有这个问题？

[rocksc30]

leetcode 里面有这个问题？

以扩展的思维去想问题，更能看清楚问题的本质。