当前位置：首页 > news >正文

LeetCode100之三数之和(15)--Java

news 2025/6/21 6:07:33

1.问题描述

给你一个整数数组 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
-105 <= nums[i] <= 105

难度等级

中等

题目链接

三数之和

2.解题思路

这道题叫做三数之和，可以看做两数之和的升级版，不过我没办法用两数之和的hash方法来做了。这一次，我选择了双指针遍历。可能你会疑惑，不是三数之和吗？怎么是双指针法，其实我们只要把其中一个数固定下来，那不就是回归两个数了吗?两个数当然就是双指针法了。

首先，我们得定义一个List集合来存储结果，还要对数组进行排序(使用双指针法的前提)。

    //用来存储结果List<List<Integer>> result = new ArrayList<>();

接着，我们就可以开始数组的遍历了。for循环先固定第一个数，这里固定数也是有讲究的，因为它要求的是三个数和为0。我们已经对数组进行排序了，所以小的数肯定在前面，大的数肯定在后面，如果我们的第一个数就已经大于0了，那么后面两个数必定大于0，也就不可能三个数相加为0，所以直接结束就好了。

        //第一个数就大于0，那三个数不可能加起来和为0if(nums[i] > 0){break;}

如果，第一个数小于0且索引不为0(防止数组越界)的话，因为题目告诉我们不包含重复的三元组，所以我们的第一个数要跳过已经使用过的数。又因为我们是排好序的，所以相同的数就在数本身的前后，我们只需要判断当前的数是否和前面的那个数相等就好了，相等我们就跳过，避免重复。

        //除去相同的整数if(i > 0 && nums[i] == nums[i-1]){continue;}

经过两轮排查之后，我们终于固定下来了第一个数，剩下的两个数我们就要从第一个数后面开始找了。定义左右两个指针，左指针从第一个数旁边开始向后走，右指针从数组的末端向前走，一个在可选范围内最小，一个在可选范围内最大。然后两个指针尝试靠拢，每一次移动，都计算一下三数之和是否为0。

        //左右指针相互靠拢int left = i+1;int right = nums.length - 1;

如果三数之和大于0，说明加多了，右指针所指的数较大，要将右指针往左移，减小一点；如果三数之和小于0，说明加少了，左指针所指的数较小，要将左指针往右移；如果三数之和等于0，那么就将这是哪个数存入一开始定义的List集合中。

            //计算当前的三数之和int sum = nums[i] + nums[left] + nums[right];if(sum > 0){//sum > 0,说明加多了，右指针要往左移right--;continue;}else if(sum < 0){//sum < 0 ,说明加少了，左指针要往右移left++;continue;}//若走到这一步，说明三数之和为0List<Integer> data = new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data);

找到一组三数之和后，不要着急着找第二组，因为题目要求不能有重复的三元组，所以我们还要将左右指针旁边与它们相同的数先跳过之后，再找下一组。

//跳过与左指针相同的整数while(left < right && nums[left] == nums[left + 1]){left++;}//跳过与右指针相同的整数while(left < right && nums[right] == nums[right- 1]){right--;}

让左右指针不断靠拢，直到左右指针相遇，找到我们所固定的第一个数的所有可能。

            //左右指针继续靠拢left++;right--;

之后重复上述操作，再重新固定一个新的数，左右指针继续移动找到将所有的数遍历完或者遇到第一个数大于0的情况退出循环，我们就找到了我们想要的所有结果。

3.代码展示

class Solution {public List<List<Integer>> threeSum(int[] nums) { //用来存储结果List<List<Integer>> result = new ArrayList<>();//对整数数组进行排序Arrays.sort(nums);for(int i = 0;i < nums.length;i++){//第一个数就大于0，那三个数不可能加起来和为0if(nums[i] > 0){break;}//除去相同的整数if(i > 0 && nums[i] == nums[i-1]){continue;}//左右指针相互靠拢int left = i+1;int right = nums.length - 1;while(left < right){//计算当前的三数之和int sum = nums[i] + nums[left] + nums[right];if(sum > 0){//sum > 0,说明加多了，右指针要往左移right--;continue;}else if(sum < 0){//sum < 0 ,说明加少了，左指针要往右移left++;continue;}//若走到这一步，说明三数之和为0List<Integer> data = new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data);//跳过与左指针相同的整数while(left < right && nums[left] == nums[left + 1]){left++;}//跳过与右指针相同的整数while(left < right && nums[right] == nums[right- 1]){right--;}//左右指针继续靠拢left++;right--;}}return result;}
}