双指针

三数之和

中等#15Java时间 O(n²)空间 O(log n),排序栈,不含输出

题目要做什么

找出数组中三个不同位置的数,使它们之和为零。返回所有不重复的三元组。

题目示例输入nums = [-1,0,1,2,-1,-4]
题目示例输出[[-1,-1,2],[-1,0,1]]

01 为什么这样做

排序后固定第一个数,在剩余区间用双指针查找。和偏小则移动左边,和偏大则移动右边;跳过重复值避免重复答案。

始终成立的条件

固定 i 后,双指针只向内移动;已跳过的重复值不会产生新的三元组。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public List<List<Integer>> threeSum(int[] nums) {3        Arrays.sort(nums);4        List<List<Integer>> ans = new ArrayList<>();5        for (int i = 0; i < nums.length - 2; i++) {6            if (i > 0 && nums[i] == nums[i - 1]) continue;7            int left = i + 1, right = nums.length - 1;8            while (left < right) {9                int sum = nums[i] + nums[left] + nums[right];10                if (sum < 0) left++;11                else if (sum > 0) right--;12                else {13                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));14                    int a = nums[left], b = nums[right];15                    while (left < right && nums[left] == a) left++;16                    while (left < right && nums[right] == b) right--;17                }18            }19        }20        return ans;21    }22}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索