15. 三数之和（算法思维系列）

15. 三数之和

• 题目
• 解题思路
• 代码

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

求三数之和，那是不是我只要从nums中取出来一个数，剩下的就是target-nums[i]，剩下的按题目要求，要分解成两数之和，这样加起来就是三数之和了。 这样来看，4数之和、5数之和，都是同理，故而可以套用nSum模板。见书323面

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        return nSumTarget(nums, 0, 3, 0);
    }


    public List<List<Integer>> nSumTarget(int[] nums, int target, int n, int start) {
        int size = nums.length;
        List<List<Integer>> res = new ArrayList<>();

        //至少要2Sum才能调用这个框架
        if (n < 2 || size < n) {
            return res;
        }

        if (n == 2) {//那就用2Sum标准的双指针那一套解法
            int lo = start;
            int hi = size - 1;

            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo];
                int right = nums[hi];

                if (sum < target) {
                    lo++;
                } else if (sum > target) {
                    hi--;
                } else {
                    //将满足条件的值添加到res
                    List<Integer> listM = new ArrayList<Integer>();
                    listM.add(left);
                    listM.add(right);
                    res.add(listM);
//题目要求的是不重复的答案，如何排除重复呢？nums[lo]==left代表出现了重复元素，那么lo还要前进，直到不是重复元素为止。
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                }
            }
        } else {//不止2Sum的规模
            //穷举nSum的第一个数，该题就是3Sum的第一个数
            for (int i = start; i < size; i++) {
                //对于target-num[i]，再进行2Sum运算
                List<List<Integer>> subs = nSumTarget(nums, target - nums[i], n - 1, i + 1);
                //如果出现满足条件的2元组，再加上 nums[i]那就是结果三元组
                for (List<Integer> sub : subs) {
                    sub.add(nums[i]);
                    res.add(sub);
                }
                //跳过重复元素
                while (i < size - 1 && nums[i] == nums[i + 1]) i++;

            }
        }


        return res;
    }
}