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

注意:

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

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

满足要求的三元组集合为:

[[-1, 0, 1], [-1, -1, 2]]


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int count = nums.length;
        if(count < 3) {
            return list;
        }
        Arrays.sort(nums);
        for(int i = 0; i < count; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int a = nums[i];
            int start = i + 1;
            int end = count - 1;
            while(start < end) {
                int b = nums[start];
                int c = nums[end];
                int sum = a + b + c;
                if(sum == 0) {
                    while (start < end && nums[start] == nums[start + 1]) {
                        ++start;
                    }
                    while (start < end && nums[end] == nums[end - 1]) {
                        --end;
                    }
                    List<Integer> arr = new ArrayList<Integer>();
                    arr.add(a);
                    arr.add(b);
                    arr.add(c);
                    list.add(arr);
                    ++start;
                    --end;
                } else if (sum < 0) {
                    ++start;
                } else {
                    --end;
                }
            }
        }
        return list;
    }
}

LeetCode 原题传送门

Q.E.D.


知识的价值不在于占有,而在于使用