LeetCode 15 三数之和超详细（难度：Medium）

绝地灬酷狼 2022-02-02 11:36 209阅读 0赞

**题目大意：给定一个包含 *n* 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 \*a，b，c ，\*使得 *a + b + c =* 0 ？找出所有满足条件且不重复的三元组。                                                                                                                     3Sum     **

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

Given an array `nums` of *n* integers, are there elements *a*, *b*, *c* in `nums` such that *a* + *b*\+ *c* = 0? Find all unique triplets in the array which gives the sum of zero.

**Example:**

Given array nums = [-1, 0, 1, 2, -1, -4],
    
    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

心情：又有好些天没刷算法了，根本原因还是不太喜欢，坚持坚持可能会好些。

刚看到题目，第一反应就是笨方法（做题太少），3层循环，挨个找出所有可能和为 0 的数字，找到了，如果我们的目标集合尚未存在当前解，就加到目标集合中。代码入下：

/**
         * 暴力解法 3层循环 超时了...
         * @param nums
         * @return
         */
        public static List<List<Integer>> threeSum(int[] nums){
    
            List<List<Integer>> result = new ArrayList<>();
    
            for (int i = 0; i < nums.length-2; i++){
                int current = nums[i];
                int twoSum = 0 - current;
                for (int j = i+1; j < nums.length-1; j++){
                    for (int k = j+1; k < nums.length; k++){
                        if (nums[j] + nums[k] == twoSum){
                            List<Integer> integers = new ArrayList<>();
                            integers.add(current);
                            integers.add(nums[j]);
                            integers.add(nums[k]);
                            boolean flag = true;
                            for (List<Integer> list : result){
                                if (list.containsAll(integers) && integers.containsAll(list)){
                                    flag = false;
                                }
                            }
                            if (flag){
                                result.add(integers);
                            }
                        }
                    }
                }
            }
    
            return result;
        }

很遗憾，结果对是对了，在 LeetCode 上提交超时了，耗时太久。。。放弃此解法

后来翻阅其他人的解决方案，找到一个略巧妙的解法：双重指针（从两边到中间），很好用，也比较容易理解。

1. 先把给定数组弄成一个有序数组， Arrays.sort(int\[\] nums);

2. 循环遍历有序数组一次，i 从 0 开始；

3. j = i + 1 ;  k = nums.length - 1 (即 nums\[j\] 为 nums\[i\] 的下一个元素，nums\[k\] 为 nums 数组的最后一个元素 )

4. while（j < k） 利用题意得到判定条件 nums\[i\] + nums\[j\] + num\[k\]

等于 0 ， 则把当前 3 个数弄成List 集合 ，加到目标集合中；

大于 0 ， 说明，和太大！需要减小最大的那个数，也就是 nums\[k\], 指针左移  k--;

小于 0 ，说明，和太小！ 需要增加数值，也就是 nums\[j\], 指针右移动，j++；

要注意的一点是 不管 nums\[i\]  nums\[j\]  nums\[k\] , 如果坐标移动之后的下一个数和之前的数是一样的该咋办？？ 还需要继续比吗？？ 肯定不需要！！ 直接跳过就好，省去多余的比较步骤！

对于 i  continue 直接到下一个

对于 j   j++

对于 k  k--

代码如下：

/**
         * 双重指针移动
         * @param nums
         * @return
         */
        public static List<List<Integer>> doublePointer(int[] nums){
            if (null == nums){
                return null;
            }
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
    
            for (int i = 0; i < nums.length - 2; i++){
                // 重复元素直接跳过
                if (i >= 1 && nums[i] == nums[i-1]){
                    continue;
                }
                int j = i + 1;
                int k = nums.length - 1;
                while (j < k){
                    if (nums[i] + nums[j] + nums[k] == 0){
                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        j++;
                        k--;
                        // 跳过重复元素，j 从前往后，所以与 j - 1 比较
                        while (j < k && nums[j] == nums[j - 1]){
                            j++;
                        }
                        // 跳过重复元素，k 从后往前，所以与 k + 1 比较
                        while (j < k && nums[k] == nums[k + 1]){
                            k--;
                        }
                    }else if (nums[i] + nums[j] + nums[k] > 0){
                        k--;
                    }else {
                        j++;
                    }
                }
            }
            return result;
        }

好了，这次通过了。 应该还有其他解法，暂时不看了。