leetcode|中等:15. 三数之和

1.题目

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• $0 <= nums.length <= 3000$
• $-10^5 <= nums[i] <= 10^5$

2. 题解

2.1 思路分析

首先对数组进行排序，排序后固定一个数 nums[i]
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
否则使用左右指针指向nums[i]后面的两端，数字分别为 nums[L]和 nums[R]计算三个数的和 sum 判断是否满足等于0
    等于0则添加进结果集
    小于0则L++(L<R)
    大于0则R--(L<R)

关于去重:
    如果 nums[i]== nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
    当 sum == 0 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++
    当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R--

2.2 代码实现

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 数组排序
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        if(nums.length>=3) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) break;

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

                int L = i + 1; // 左指针
                int R = nums.length - 1; // 右指针

                while (L < R) {
                    while (L < R && nums[L] == nums[L + 1]) L++; // 去重
                    while (L < R && nums[R] == nums[R - 1]) R--; // 去重
                    int sum = nums[i] + nums[L] + nums[R];
                    if (sum == 0) {
                        res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                        L++;
                        R--;
                    } else if (sum < 0) {
                        L++;
                    } else {
                        R--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

2.3 提交结果

参考资料

1. https://leetcode-cn.com/problems/3sum/
2. https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/