解题报告， 这个做的比较绝望， 用了two points, recursion, memorization= =, 思路很简单， 就是边界条件比较难办， 还有去重什么的 ， 算是入门级吧
public class Solution { public List> fourSum(int[] nums, int target) { List> result = new ArrayList<>(); Arrays.sort(nums); // start and end boundary int[][] hash = new int[nums.length][nums.length]; for (int i = 0; i< nums.length; i ++){ for(int j = nums.length -1; j >= 0; j--){ if(hash[i][j] > 0) break; hash[i][j] = 1; hash[j][i] = 1; if(i+1 < j -1 &&nums[i] == nums[j]){ int tempSum = nums[i]*4; if(tempSum == target) { result.add(Arrays.asList(nums[i],nums[i], nums[i], nums[i])); // return result; } i = i + 1; j = j -1; } getSum(nums, target, i, j, result); } } return result; } private void getSum(int[] nums, int t, int start, int end, List> result){ if(start >= end) return; int s = start + 1; int e = end - 1; // if(s > e) return; while(s < e){ int sum = nums[s] + nums[e] + nums[start] + nums[end]; if(sum == t){ Listtemp = new ArrayList<>();
temp.add(nums[start]);
temp.add(nums[s]);
temp.add(nums[e]);
temp.add(nums[end]);
while(s + 1 < e && nums[s] == nums[s + 1]) s++;
while(e - 1 > s && nums[e] == nums[e - 1]) e--;
s++;
e--;
if(result.contains(temp)){
continue;
}else{
result.add(temp);
}
}else if(sum < t){
s++;
}else{
e--;
}
}
}
}
