网站底部代码大全,微信网页版还能用吗,专门做水产海鲜的网站吗,高级网站开发工程师证文章目录 题目方法一#xff1a;双指针#xff08;定2动2#xff09; 题目 方法一#xff1a;双指针#xff08;定2动2#xff09;
这题可以参考【LeetCode-中等题】15. 三数之和 区别在于#xff0c;三数之和只需要用一个for循环定住一个数#xff0c;然后设置两个前… 文章目录 题目方法一双指针定2动2 题目 方法一双指针定2动2
这题可以参考【LeetCode-中等题】15. 三数之和 区别在于三数之和只需要用一个for循环定住一个数然后设置两个前后指针来根据sum的值和目标值比较来滑动指针
那么这题也是同理的我们需要做的事就是定住2个数要用两个for循环定住两个数然后设置两个前后指针来根据sum的值和目标值比较来滑动指针
里面的处理细节很多需要注意提前处理一些不可能满足条件的情况减少时间复杂度
class Solution {
//for定2 指针动2public ListListInteger fourSum(int[] nums, int target) {int len nums.length;if(nums null||len 4 ) return new ArrayList();ListListInteger res new ArrayList();ListInteger zres null;Arrays.sort(nums);for(int i 0 ;i len-3 ;i){//本身就是排序的数组 若第一个数就大于等于target了那么再加上任何一个数都会大于target所以直接break// if(nums[i]target) break;//这个条件不能要对比LeetCode 15. 三数之和 如果target是负数第一个数大于target 在往下加可能会越来越小也是可以taget的//但是如果target为0或正数那么第一个数大于target 往下加会越来越大//去重操作 如果nums[i]nums[i-1] 会得到一份与nums[i-1]一样的结果集if(i0nums[i]nums[i-1]) continue;// 若以i开头的四个元素就已经大于target了 那就无需做任何操作了没必要了在往后面加再怎么也会大于targetif((long)nums[i]nums[i1]nums[i2]nums[i3] target) break;// 若以i开头元素和数组末尾的三个元素就还小于target了 那就没必要做此次循环毕竟i加上后面最大的三个数都比target小if((long)nums[i]nums[len-1]nums[len-2]nums[len-3] target) continue;for(int j i1 ;j len-2 ;j){//这里就和 LeetCode 15. 三数之和 一样的原理 唯一多了一个提前判断// 这里的三个if与上面同理 if(ji1nums[j]nums[j-1]) continue;if((long)nums[i]nums[j]nums[j1]nums[j2] target) break;if((long)nums[i]nums[j]nums[len-1]nums[len-2] target) continue;int left j1;int right len-1;while(left right){long sum (long) nums[i]nums[j]nums[left]nums[right];if(sum target) {zres new ArrayList();//满足要求的子结果集zres.add(nums[i]);zres.add(nums[j]);zres.add(nums[left]);zres.add(nums[right]);res.add(zres);//加入大结果集while(left right nums[left]nums[left1]) left;//两个指针的去重while(left right nums[right]nums[right-1]) right--;left;//移动指针到不重复的新区域right--;}else if(sum target) right--;//缩小数值else left;//扩大数值}}}return res;}
}
