15. 三数之和

crazyjums

LeetCode刷题双指针middle

发布于：Nov 12, 2020

次浏览

15. 三数之和

https://leetcode-cn.com/problems/3sum/

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1 解题思路

排序+双指针

定义三个指针$a,b,c$，然后固定其中一个，移动其中两个，假设固定$a$，然后令$b=a+1$，$c=size-1$，移动指针$b$和$c$。有以下三种情况：

大于0：即$nums[a]+nums[b]+nums[c]>0$，此时应该指针$d$左移
小于0：即$nums[a]+nums[b]+nums[c]<0$，此时应该指针$c$右移
等于0：添加到结果集

注意：题目中说结果集中不能含有重复结果，所以需要判断相邻元素的值是否相等，相等则跳过。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int size = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i <= size - 2; i ++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; //去重
            int l = i + 1;
            int r = size - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] > 0) {
                    r --;
                } else if (nums[i] + nums[l] + nums[r] < 0) {
                    l ++;
                } else {
                    List<Integer> tem = new ArrayList<>();
                    tem.add(nums[i]);
                    tem.add(nums[l]);
                    tem.add(nums[r]);
                    ans.add(tem);
                    while (l < r && nums[l] == nums[l + 1]) l ++; //去重
                    while (l < r && nums[r] == nums[r - 1]) r --; //去重
                    l ++;
                    r --;
                }
            } 
        }
        return ans;
    }
}