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. 解题
直接上官方的示例结果: (PS:官方的注释已经写的很多了,就直接用官方的代码了。)
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 first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同, 除下标为0的数,如果当前值和上一轮的值相同,就跳过本次循环执行下一轮新的循环。
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
//third 对应的指针初始指向数组的最右端 。定义值为C
int third = n - 1;
int target = -nums[first]; //当前数值的负数作为目标值,也就是目标target+nums[first]=0; 定义值为A
// 循环枚举其中的 B值, 满足A+C+B=0;
// 开始位置为 当前下标的后一位,到数组长度
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同,如果相同就跳过当前循环进入下一轮循环。
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧,如果B+C >target 就代表不能满足A+B+C=0;C的坐标就往后缩减。
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环。A,C值重新再获取
if (second == third) {
break;
} //如果满足,那么就进行数组的添加。
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
执行用时: 21 ms
内存消耗: 45.9 MB
可是速度效率不咋的啊。 优化了之后,速度提高了,内存占用变大了。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
int len = nums.length;
if (len <= 2) {
return lists;// 直接返回为空
}
//排序,将混乱的数组,按照从小到大的顺序进行排序
Arrays.sort(nums);
int tmp;
int L, R,a; //用于标注 左边和右边的下标。
for (int i = 0; i < len; ++i) { //循环整个数组
a = nums[i]; // 得到当前的值,该值就是 a+b+c 中的 a
if (a > 0) return lists; // 如果当前的值为0以上的数,则停止循环。
if (i > 0 && a == nums[i - 1]) // 如果不是第一个数,并且当前与前一个数相同。那么跳过直到不同为止。 必须比较前一个数,否则会有遗漏。
continue; //结束本次循环 i++ 进入下一轮循环。
L = i + 1;// b的数值 从i+1 开始循环
R = len - 1; // c的值,从len-1开始循环
while (L < R) { // 只要右侧下标 大于左侧下标就循环,如果里面配置不到位容易陷入死循环
tmp = a + nums[L] + nums[R];// 得到当前累加结果
if (tmp == 0) { // 满足要求,a+b+c =0
List<Integer> list = new ArrayList<>();
list.add(a);
list.add(nums[L]);
list.add(nums[R]);
lists.add(list);
// 如果当前两个值都相同,那么避免出现重复,需要修改某个值 直到是否有相同的。
while (L < R && nums[L + 1] == nums[L]) // 左侧值进行逼近,
++L;
while (L < R && nums[R - 1] == nums[R])
--R;//右侧值进行循环逼近
++L;
--R;
} else if (tmp < 0) { // 不满足需求,但如果结果值小于0 ,就移动左侧
++L;
// } else if (a + nums[L] < nums[i] || a + nums[L] > nums[L]) {
// break;
} else {//其他情况下,就移动右侧值
--R;
}
}
}
return lists;
}
}
执行用时: 17 ms
内存消耗: 46.1 MB
上面的解法都是,通过排序+双指针进行的。
参考链接:
评论区