15.三数之和 || 双指针

15.三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

基本思路

这一题要注意和两数之和的区别 : 两数之和的结果仅仅有一个, 而三数之和有多个结果并且不能重复

基本思路是 :

固定三数中的其中一个 , 比如 [i, j, k] 固定 i , (nums中的所有值都可以成为i)
然后使用 twoSum(nums, j, k, target) 找打合适的 j 和 k

但是题目要求 nums[i] + nums[j] + nums[k] = 0 , 满足 i != j、i != k 且 j != k , 并且所有的三元组必须都是不重复的

因为数组是排好序的, 只要有两个相同的 i , 那么一定会出现重复的 [i, j, k] , 因为 i 相同, 传入 twoSum() 中对应的 nums 也是重合的

解决方法 :

对于外层 i 来说 , 我们需要跳过重复的 i : if (i > 0 && nums[i] == nums[i - 1]) continue;

			 for (int i = 0; i < nums.length; i++) {

                if (i > 0 && nums[i] == nums[i - 1]) continue;

                // 获取 每个 i 对应所有满足条件的 twoSum
                List<List<Integer>> allTwoSumResult = twoSum(nums, i + 1, 0 - nums[i]);
                for (List<Integer> result : allTwoSumResult) {
                    results.add(Arrays.asList(nums[i], result.get(0), result.get(1)));
                }
            }

对于 twoSum 来说 , 我们也需要跳过相同的 j :

	for (int i = start; i < nums.length; i++) {

                // 因为 : 排序后, 相同的数字会排在一块,
                // 跳过重复的
                if (i > start && nums[i] == nums[i - 1]) continue;

                // 移动 j 到满足条件的位置
                while (j > i && nums[j] + nums[i] > target) j--;

                if (j > i && nums[j] + nums[i] == target) {
                    allTwoSumResult.add(Arrays.asList(nums[i], nums[j]));
                }
	 }

无论对于 i = 1 还是 i = 2 来说, 都可以得到 [-1, 2] 这一组满足条件的值(因为数组是排好序的), 所以我们需要把相同的剔除

代码实现

class Solution2 {
        public List<List<Integer>> threeSum(int[] nums) {

            Arrays.sort(nums);

            // 思路 :
            // result = [[i,j,k]] 固定一个 k = ? , target = 0
            // twoSum(i, j) = 0 - k
            // 找到所有的合适的 k 直接放入List中即可
            // 根本思路是 : 已经用过的就不能在用了, 不然就会出现重复的
            List<List<Integer>> results = new ArrayList<>();
            // i < j < k
            for (int i = 0; i < nums.length; i++) {
                // 获取 每个 i 对应所有满足条件的 twoSum
                List<List<Integer>> allTwoSumResult = twoSum(nums, i + 1, 0 - nums[i]);
                for (List<Integer> result : allTwoSumResult) {
                    results.add(Arrays.asList(nums[i], result.get(0), result.get(1)));
                }

                while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
            }
            return results;
        }

        /**
         * @param nums
         * @param start  这个值很关键, 目的是防止重复的数字被使用
         * @param target
         * @return
         */
        private List<List<Integer>> twoSum(int[] nums, int start, int target) {
            // 找到所有满足target的值
            List<List<Integer>> allTwoSumResult = new ArrayList<>();
            // 双指针法 (前提 : 数组必须是排好序的)
            int i = start, j = nums.length - 1;
            while (j > i) {
                int left = nums[i], right = nums[j];
                int sum = nums[i] + nums[j];

                if (sum > target) {
                    j--;
                } else if (sum < target) {
                    i++;
                } else {
                    allTwoSumResult.add(Arrays.asList(left, right));
                    // 移动 i ,跳过所有
                    while (i < j && nums[i] == left) i++;
                    while (i < j && nums[j] == right) j--;
                }
            }
            return allTwoSumResult;
        }
    }

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {

            Arrays.sort(nums);

            List<List<Integer>> results = new ArrayList<>();
            // i < j < k
            for (int i = 0; i < nums.length; i++) {

                if (i > 0 && nums[i] == nums[i - 1]) continue;

                // 获取 每个 i 对应所有满足条件的 twoSum
                List<List<Integer>> allTwoSumResult = twoSum(nums, i + 1, 0 - nums[i]);
                for (List<Integer> result : allTwoSumResult) {
                    results.add(Arrays.asList(nums[i], result.get(0), result.get(1)));
                }
            }
            return results;
        }

        /**
         * @param nums
         * @param start  这个值很关键, 目的是防止重复的数字被使用
         * @param target
         * @return
         */
        private List<List<Integer>> twoSum(int[] nums, int start, int target) {
            // 找到所有满足target的值
            List<List<Integer>> allTwoSumResult = new ArrayList<>();
            int j = nums.length - 1;
            for (int i = start; i < nums.length; i++) {

                // 因为 : 排序后, 相同的数字会排在一块,
                // 跳过重复的
                if (i > start && nums[i] == nums[i - 1]) continue;

                // 移动 j 到满足条件的位置
                while (j > i && nums[j] + nums[i] > target) j--;

                if (j > i && nums[j] + nums[i] == target) {
                    allTwoSumResult.add(Arrays.asList(nums[i], nums[j]));
                }
            }

            return allTwoSumResult;
        }
}