leetcode-15.三数之和

题目链接

15.三数之和

代码

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

        int n = nums.length;

        // 有序之后才可以用左右指针来根据元素大小进行移动
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        int a, b, c;

        // 固定一个最小元素，再左右指针去找另外两个元素
        for (int i = 0; i < n - 2; i++) {
            // a 为最小元素，若最小元素大于 0 则和不可能为 0，跳出
            if ((a = nums[i]) > 0) break;

            // 跳过相同的元素
            if (i != 0 && nums[i] == nums[i - 1]) continue;

            // 左指针从 i + 1 开始，向右移动
            // 右指针从 n - 1 开始，向左移动
            for (int j = i + 1, k = n - 1; j < k;) {
                b = nums[j];
                c = nums[k];

                int sum = a + b + c;

                if (sum == 0) {
                    res.add(Arrays.asList(a, b, c));

                    // 跳过相同的元素，注意这里是 ++j 即为非相同元素下标
                    while (j < k && nums[j] == nums[++j]);
                    while (j < k && nums[k] == nums[--k]);
                } else if (sum < 0) {
                    // 和小于 0 需要一个更大的数字，左指针右移
                    ++j;
                } else {
                    // 和大于 0 需要一个更小的数字，右指针左移
                    --k;
                }
            }
        }

        return res;
    }
}

复杂度分析

• 时间复杂度: O(N^2)
• 空间复杂度: O(logN) 额外的排序所使用的空间复杂度

相似题目

• 1.两数之和