[Link] https://leetcode.com/problems/maximum-subarray/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new LinkedList<> ();
int l = nums.length;
Arrays.sort(nums);
for(int i = 0; i < l - 3; i++) { // i j start end
if(i != 0 && nums[i-1] == nums[i]) continue;
if(nums[i] * 4 > target) break;
for(int j = i+1; j < l - 2; j++) {
if(j != i+1 && nums[j-1] == nums[j]) continue;
int start = j+1, end = l - 1,targetNum = target - nums[i] - nums[j];
while(start < end) {
if(nums[start] + nums[end] == targetNum) {
List<Integer> ele = Arrays.asList(nums[i], nums[j], nums[start] , nums[end]);
list.add(ele);
while(start < end && nums[start] == nums[start + 1]) start++;
while(start < end && nums[end - 1] == nums[end]) end--;
start++;
end--;
} else if(nums[start] + nums[end] < targetNum) start++;
else end--;
}
}
}
return list;
}
}