大家好！我是曾续缘😋
今天是《LeetCode 热题 100》系列
发车第 6 天
双指针第 3 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵
难度：💖💖

解题方法

排序是很容易想到的, 为了不重复的遍历，我们假设i < j < k。

使用一个for循环的代价，当我们固定一个i, 问题就是求nums[j] + nums[k] == -nums[i]了, 我们要求出所有的下标(j,k)满足上面的等式。

同样的，使用一个for循环的代价，假设我们固定j，只需要在数组中寻找合适的k了。

在使用一个for循环，显然不行，这时我们使用双指针来利用j的for循环：

因为数组是升序的, 向后移动j就可能会导致nums[j]值增加, 如果前一个步骤中nums[k]是满足条件的, 现在nums[j]值增加了, nums[k]就不满足条件了, 之后的nums[k+1]等更大, 更加不符合条件, 因此我们可以利用前一个步骤中k的位置接着判断, 进而减少了一次循环.（简而言之就是j指针的向后移动只会使得k指针向前移动，nums[j]值增加，nums[k]值就需要减少）

i使用一个for循环代价，排序后因为单调性，j和k可用双向指针，共用一个for循环代价。

Code

查看代码

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int k = n - 1;
            for(int j = i + 1; j < n; j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                while(j < k && nums[i] + nums[j] + nums[k] > 0){
                    k--;
                }
                if(j == k){
                    break;
                }
                if(nums[i] + nums[j] + nums[k] == 0){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

解题方法 ​

Code ​

解题方法

Code