不会做,参考了代码随想录和力扣官方题解,对此题进行整理。
X数之和
- 15. 三数之和
- 代码思路
- 20240103重写
- 错误1
- 错误2
- Java语言点总结
- 18. 四数之和
- 代码思路
- 20240104
- (伪)错误1 第一次剪枝
- 错误2 第二次剪枝
- 错误3 溢出
15. 三数之和
代码思路
思想:利用双指针法,对数组从小到大排序。先固定一个数,找到其他两个。
(1)首先对数组从小到大排序。
(2)a从左到右遍历数组,每一次遍历的时候设置left指针,right指针。num[a]+num[left]+num[right],如果值等于0,相当于找到了目标元组。如果值大于0,right–;如果值小于0,left++。
(3)涉及到去重的问题。a、left、right都会重复,具体请看下图(↑指a; -指left; =指right)。
a去重:如果在这次循环之前,已经判断了三元组之一的元素num[a](不管是符合条件还是不符合条件,已经判断过这个元素),都跳过。if (num[a] >num[a-1]) continue;
为什么这里不用num[a]和num[a+1]比较,因为会出现元组 -1 -1 2。这是符合条件的。num[a] 和num[a-1]保证的是,在本次循环之前已经判断过这个元素;num[a]和num[a+1]比较还continue的话就是不允许三元组里有重复的元素。
left去重、right去重:找到一个目标元组之后,(且上一步a去重),现在要对left、right去重。如果num[left+1] =num[left], left++;如果num[right-1] =num[right], right–。
(4)技巧:三个数num[a]、num[left]、num[right]相加等于零,因为初始值 left=a+1,right=num.length-1,所以a<left<right这个等式恒成立。又因为num数组从小到大排序,三个数中最小的是a,如果a>0,那么一定不存在这个元组。
20240103重写
20240103第一次重写,错了很多,对着答案改。
语言是 java。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 不知道怎么初始化List<List<Integer>> ans = new ArrayList<ArrayList<Integer>>();
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);//写错了Arrays.sort(),我写少了一个s
int left,right;
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
return ans;
}
if(i>0 && nums[i]==nums[i-1]) { //是i>0,不是i>1
continue;
}
left = i+1;
right = nums.length-1;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0) {
right--;
} else if(sum < 0) {
left++;
} else {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));//不会写
while(right > left && nums[left+1] == nums[left]) {left++;}//为什么要设置right > left
while(right > left && nums[right-1] == nums[right]) {right--;}
//漏写了。
right--;
left++;
}
}
}
return ans;
}
}
错误1
错误:我在代码中写了
List<List<Integer>> a=new ArrayList<ArrayList<Integer>>();
报错信息:ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>
List<List<Integer>>
是在List1<>中再放一个List2<>,List1中每个List2的长度可以是任意的,而不是像二维数组那样维度固定。
List<List<Integer>>
的初始化为 List<List<Integer>> a=new ArrayList<List<Integer>>();
这个与泛型有关,但我还没学到那里,CSDN 有一篇文章讲的不错:跳转链接
错误2
有可能会出现 -2 1 1 1 1 1 1 1 的情况,所以 left++ right- -的时候一定要保证 left<right
Java语言点总结
- Arrays.sort()
List<List<Integer>>
的初始化为List<List<Integer>> a=new ArrayList<List<Integer>>();
- Arrays.asList() 该方法是将数组转化成List集合的方法
- List中 用add方法添加成员
18. 四数之和
代码思路
和三数之和一样。
五数、六数之和都是一样的。
20240104
又看了代码随想录的分析才写出来的。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for(int k = 0; k < nums.length; k++) { // nums.size 是否有必要?
if(k > 0 && nums[k] == nums[k-1]) {
continue;
}
if(nums[k]>0 && nums[k]>target) {//错了 if(target>0 && nums[k]>target)
return ans;
}//如果target小于零,nums[k]>target 不能跳过 [-4,-1,0,0] TARGET=-5
for(int i = k+1; i < nums.length; i++) {
if(i > k+1 && nums[i] == nums[i-1]) {
continue; // i=k+1,nums[k+1]=nums[k]不能跳过
}
if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
break;//这里是break不是return
}
int left = i+1;
int right = nums.length-1;
while(left < right) {
long sum =(long) nums[left] + nums[right] + nums[k] +nums[i];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
ans.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
while(left < right && nums[left+1] == nums[left]) left++;
while(left < right && nums[right-1] == nums[right]) right--;
left++;
right--;
}
}
}
}
return ans;
}
}
(伪)错误1 第一次剪枝
最开始写成: if(target>0 && nums[k]>target)
代码随想录写法:if(nums[k]>0 && nums[k]>target)
刚刚又试了一下,其实都是对的。之前报错是因为第二次剪枝的break和return出错。
错误2 第二次剪枝
最开始写成:
if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
return;
}
正确写法:
if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
break;
}
对比了代码随想录C++的代码(代码随想录Java的代码没有第二次剪枝),我一直以为是大于等于出错,或者是 &&的左右顺序出错,其实是 break和 return的区别。