jsp和php哪个做网站快,手机编程工具,建网站平台,品质好货四数之和
中等 给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] #xff08;若两个四元组元素一一对应#xff0c;则认为两个四元组重复#xff09;#xf…四数之和
中等 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
思路
将数组进行排序排序后进行三层遍历第一层遍历遍历当前数字以及之后的三位数字求和得到的结果大于目标值说明不存在等于目标值的以及末尾的三位数字得到的结果如果小于目标值则摆脱当前值的循环减少内存消耗。第二层遍历同样的对他的以及第一层遍历的值作为底将后续的两位数字求和结果如果大那么跳出循环以及末尾的两位数字结果如果小则跳出该值循环。说明这两层遍历的范围不在目标值中。第三层遍历进行左右双指针遍历。得到的结果进行比较如果小那么左指针后移如果大那么右指针左移。
代码
class Solution {public ListListInteger fourSum(int[] nums, int target) {int n nums.length;ListListInteger re new ArrayListListInteger();if(n4){return re;}Arrays.sort(nums);for(int i 0;in-3;i){if (i 0 nums[i] nums[i - 1]) {continue;}if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) {break;}if ((long) nums[i] nums[n - 3] nums[n- 2] nums[n - 1] target) {continue;}for(int j i1;jn-2;j){if (j i 1 nums[j] nums[j - 1]) {continue;}if ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) {break;}if ((long) nums[i] nums[j] nums[n - 2] nums[n - 1] target) {continue;}int p j1;int q n-1;while(pq){long sum (long) nums[i]nums[j]nums[p]nums[q];ListInteger li new ArrayList();li.add(nums[i]);li.add(nums[j]);li.add(nums[p]);li.add(nums[q]);if(sum target){re.add(li);while(pqnums[p]nums[p1]){p;}p;while(pqnums[q]nums[q-1]){q--;}q--;}else if(sumtarget){p;}else{q--;}}}}return re;}
}
