LeetCode刷题 day10

目录1.最接近的三数之和2.四数之和1.最接近的三数之和给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个在 不同下标位置 的整数使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。示例 1输入nums [-1,2,1,-4], target 1输出2解释与 target 最接近的和是 2 (-1 2 1 2)。示例 2输入nums [0,0,0], target 1输出0解释与 target 最接近的和是 00 0 0 0。思路排序双指针排序时间复杂度为O(nlogn)双指针遍历O(n)因此整体时间复杂度是O(nlogn),如果是暴力解法是O(n^2)因此优于暴力算法classSolution{publicintthreeSumClosest(int[]nums,inttarget){Arrays.sort(nums);intminSum1_00_0001;intnnums.length;for(inti0;in-2;i){//判断左边界//这里加了优化如果最左边三个元素和大于target则后续不用遍历因为根据数组有序性其他元素和更是大于target取当前最小值即可intcurSumnums[i]nums[i1]nums[i2];if(curSumtarget){minSumMath.abs(target-curSum)Math.abs(minSum-target)?curSum:minSum;continue;}//判断右边界//分析同上curSumnums[i]nums[n-1]nums[n-2];if(curSumtarget){minSumMath.abs(target-curSum)Math.abs(minSum-target)?curSum:minSum;continue;}curSumnums[i]nums[i1]nums[i2];intji1,kn-1;curSumnums[i]nums[j]nums[k];while(jk){minSumMath.abs(target-curSum)Math.abs(minSum-target)?curSum:minSum;if(curSumtarget){curSum-nums[k];k--;curSumnums[k];}else{curSum-nums[j];j;curSumnums[j];}}}returnminSum;}}时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)空间复杂度O ( 1 ) O(1)O(1)2.四数之和给你一个由 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]]思路同上一题思路一样排序加双指针暴力解法是四层遍历时间复杂度为O(n4)而双指针时间复杂度为O(n3)classSolution{publicListListIntegerfourSum(int[]nums,inttarget){//先排序Arrays.sort(nums);ListListIntegeransnewArrayList();intnnums.length;for(inti0;in-3;i){//这里有小优化判断当前是否与前一个循环的元素相同保持每个四元组只有一个if(i0nums[i]nums[i-1]){continue;}for(intji1;jn-2;j){//这里同样的优化目的也是为了保证四元组的唯一性if(ji1nums[j]nums[j-1]){continue;}longremains(long)target-nums[i]-nums[j];if(nums[j1]nums[j2]remains||nums[n-2]nums[n-1]remains){continue;}for(intkj1,ln-1;kl;){intsumnums[k]nums[l];if(sumremains){ListIntegerlistList.of(nums[i],nums[j],nums[k],nums[l]);ans.add(list);k;while(klnums[k]nums[k-1]){k;}l--;while(klnums[l]nums[l1]){l--;}}elseif(sumremains){k;}else{l--;}}}}returnans;}}时间复杂度O ( n 3 ) O(n^3)O(n3)空间复杂度O ( 1 ) O(1)O(1)