# 37lines O(n3) beats 99.16% of java submission

• ``````public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new LinkedList<>();
// we sort the arrays O(n log(n));
Arrays.sort(nums);
// from i = 0, to i - 3 possibilities
for(int i=0; i< nums.length - 3; i++) {
// we check repetition and boundaries.
if(i > 0 && nums[i-1] == nums[i]
|| nums[i] * 4 > target
|| nums[nums.length-1]*3 + nums[i] < target) continue;
threeSum(nums, i+1, nums[i], target, res);
}
return res;
}

public void threeSum(int[] num, int start, int value, int target, List<List<Integer>> res) {
for(int i = start; i < num.length ;i++) {
// we check boundaries and repetitions
if(value + num[i] + 2 * num[num.length-1] < target
|| value + num[i] * 3 > target
|| (i > start && num[i-1] == num[i])) continue;
int j = i+1, k = num.length-1;
while(j < k) {
if(value+num[j]+num[k]+num[i] == target) {
res.add(Arrays.asList(value, num[i], num[j], num[k]));
while (j < k && num[j] == num[j+1]) j++;
while (j < k && num[k] == num[k-1]) k--;
j++; k--;
}
// We shift the two pointers until we have a new == 0, we stop if j==k
while(j < k && (value+num[j]+num[k]+num[i] < target)) j++;
while(j < k && (value+num[j]+num[k]+num[i] > target)) k--;
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.