算法训练营第十四天|18.四数之和

第14天 18. 四数之和建议 要比较一下本题和 454.四数相加II 的区别为什么 454.四数相加II 会简单很多这个想明白了对本题理解就深刻了。 本题 思路整体和 三数之和一样的都是双指针但写的时候 有很多小细节需要注意建议先看视频。题目链接https://leetcode.cn/problems/4sum/ 视频讲解https://www.bilibili.com/video/BV1DS4y147USpublic class Demo3 {public ListListInteger fourSum(int[] nums,int target){ListListInteger resultnew ArrayList();if (numsnull||nums.length4) {return result;}Arrays.sort(nums);int nnums.length;for (int i 0; i n-3; i) {if (i0nums[i]nums[i-1]) continue;if((long)nums[i]*4target) break;if((long)nums[i]nums[n-3]nums[n-2]nums[n-1]target) continue;for (int j i1; j n-2; j) {if(ji1nums[j]nums[j-1]) continue;if((long)nums[i]nums[j]*3target) break;if((long)nums[i]nums[j]nums[n-2]nums[n-1]target) continue;int leftj1,rightn-1;while (leftright) {long sum(long) nums[i]nums[j]nums[left]nums[right];if (sumtarget) {result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(leftrightnums[left]nums[left1]) left;while(leftrightnums[right]nums[right-1]) right--;left;right--;}else if (sumtarget) {left;}else {right--;}}}}return result;}public static void main(String[] args) {Scanner innew Scanner(System.in);Demo3 demo3new Demo3();System.out.println(length:);int nin.nextInt();int[] numsnew int[n];System.out.println(数组);for (int i 0; i nums.length; i) {nums[i]in.nextInt();}System.out.println(target);int targetin.nextInt();System.out.println(demo3.fourSum(nums, target));}}