与三数之和一样的思路。前两个数两个循环,后两个数用指针遍历的方式。在整体循环框架、指针遍历码好后,要添加条件来增加遍历速度,以及去重。
提交代码
import java.util.*;
import static java.lang.Math.min;
public class leetcode {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
String str = scan.nextLine();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
int target = scan.nextInt();
List result = fourSum(nums, target);
System.out.println(result);
}
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
if(nums == null || len < 4) return ans;
Arrays.sort(nums);
for(int i = 0; i<len-3 ; i++) {
if( i>0 && nums[i] == nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
for(int j = i+1; j<len-2; j++) {
if( j>i+1 && nums[j] == nums[j-1]) continue;
int L = j + 1;
int R = len - 1;
while(L < R) {
int sum = nums[i] + nums[j] + nums[L] + nums[R];
if(sum == target) {
ans.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
while (L < R && nums[L] == nums[L+1]) L++;
while (L < R && nums[R] == nums[R-1]) R--;
L++;
R--;
}
else if (sum - target < 0) L++;
else if (sum - target > 0) R--;
}
}
}
return ans;
}
}
原文:https://www.cnblogs.com/chenshaowei/p/12641326.html