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

第14天 18. 四数之和
建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。

题目链接：https://leetcode.cn/problems/4sum/ 视频讲解：https://www.bilibili.com/video/BV1DS4y147US

public class Demo3 {
public List<List<Integer>> fourSum(int[] nums,int target){
List<List<Integer>> result=new ArrayList<>();
if (nums==null||nums.length<4) {
return result;
}
Arrays.sort(nums);
int n=nums.length;
for (int i = 0; i < n-3; i++) {
if (i>0&&nums[i]==nums[i-1]) continue;
if((long)nums[i]*4>target) break;
if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for (int j = i+1; j < n-2; j++) {
if(j>i+1&&nums[j]==nums[j-1]) continue;
if((long)nums[i]+nums[j]*3>target) break;
if((long)nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while (left<right) {
long sum=(long) nums[i]+nums[j]+nums[left]+nums[right];
if (sum==target) {
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left<right&&nums[left]==nums[left+1]) left++;
while(left<right&&nums[right]==nums[right-1]) right--;
left++;right--;
}
else if (sum<target) {
left++;
}
else {
right--;
}
}
}
}
return result;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
Demo3 demo3=new Demo3();
System.out.println("length:");
int n=in.nextInt();
int[] nums=new int[n];
System.out.println("数组：");
for (int i = 0; i < nums.length; i++) {
nums[i]=in.nextInt();
}
System.out.println("target");
int target=in.nextInt();
System.out.println(demo3.fourSum(nums, target));
}
}