Clean accepted java O(n^3) solution based on 3sum

• ``````public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
ArrayList<List<Integer>> ans = new ArrayList<>();
if(num.length<4)return ans;
Arrays.sort(num);
for(int i=0; i<num.length-3; i++){
if(num[i]+num[i+1]+num[i+2]+num[i+3]>target)break; //first candidate too large, search finished
if(num[i]+num[num.length-1]+num[num.length-2]+num[num.length-3]<target)continue; //first candidate too small
if(i>0&&num[i]==num[i-1])continue; //prevents duplicate result in ans list
for(int j=i+1; j<num.length-2; j++){
if(num[i]+num[j]+num[j+1]+num[j+2]>target)break; //second candidate too large
if(num[i]+num[j]+num[num.length-1]+num[num.length-2]<target)continue; //second candidate too small
if(j>i+1&&num[j]==num[j-1])continue; //prevents duplicate results in ans list
int low=j+1, high=num.length-1;
while(low<high){
int sum=num[i]+num[j]+num[low]+num[high];
if(sum==target){
while(low<high&&num[low]==num[low+1])low++; //skipping over duplicate on low
while(low<high&&num[high]==num[high-1])high--; //skipping over duplicate on high
low++;
high--;
}
//move window
else if(sum<target)low++;
else high--;
}
}
}
return ans;
}
``````

• nice answer! you can add a link to 3 sum , so people can see their similarity

• This post is deleted!

• @casualhero

sorry to know it got TLE now

• @Lara
Add the following sentence could avoid TLE, and win over more than 80%.
if(4 * nums[0] > target || 4 * nums[len - 1] < target) return result;

• @CrazyT good idea

• I use the method also base on 3sum
""
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length-3;){
threeSum(nums, i, target-nums[i], list);
do{i++;}while(i<nums.length-3&&nums[i]==nums[i-1]);
}
return list;
}

``````public void threeSum(int[] nums,int index, int target,List<List<Integer>> list )
{
int height,low,subRes;
for(int i=index+1;i<nums.length-2;)
{
low=i+1;height=nums.length-1;
while(low<height)
{
subRes=nums[i]+nums[low]+nums[height];
if(subRes==target)
{
list.add(new ArrayList<Integer>(Arrays.asList(new Integer(nums[index]),new Integer(nums[i]),new Integer(nums[low]),new Integer(nums[height])) ));
if(nums[low]==-2&&nums[height]==0)
System.out.println("*****debug*****");
do{low++;height--;}while(low<height&&nums[low]==nums[low-1]&&nums[height]==nums[height+1]);
}
else{
if(subRes>target) {height--;}
else {low++;}
}
}
do{i++;}while(i<nums.length-2&&nums[i]==nums[i-1]);
}
}``````

I wonder if anyone could explain here, why, while the first two elements of the quadruple can 'skip' the replicate (the 2 'continue'), the last two elements (marked by 'low' and 'high') only do the 'skipping' when we found a valid quadruple?

Thanks!

• @CrazyT Hi, why add this line of code? Thank you so much.

• @Lara Where exactly should that line be added?

• Inspired by the top1 "7ms solution", add two more condition sentences in each “for()” loops will save a lot of runtime which only 26ms,can beats 98.16%;

``````public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
if(nums.length<4) return res;
Arrays.sort(nums);
for(int i=0;i<nums.length-3;i++){
if(i>0&&nums[i]==nums[i-1]) continue;

if(nums[i]*4>target) break;// Too Big!!
if(nums[i]+3*nums[nums.length-1]<target) continue;//Too Small

for(int j=i+1;j<nums.length-2;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue;

if(nums[j]*3>target-nums[i]) break;//Too Big
if(nums[j]+2*nums[nums.length-1]<target-nums[i]) continue;// Too Small

int begin=j+1;
int end=nums.length-1;
while(begin<end){
int sum=nums[i]+nums[j]+nums[begin]+nums[end];
if(sum==target){
while(begin<end && nums[begin]==nums[begin+1]){begin++;}
while(begin<end && nums[end]==nums[end-1]){end--;}
begin++;
end--;
}else if (sum<target){
begin++;
}else{
end--;
}
}
}
}
return res;
}
}
``````

• @61m nice optimizations. I have updated the post with them

• d by 'low' and 'high

the fist two prevents duplicate results. in the windows I skip over duplicates in order to find other possible results

• if(nums[i]4>target) break;// Too Big!!
if(nums[i]+3
nums[nums.length-1]<target) continue;//Too Small

Please let me know what the purpose of multilying by 4 or 3

• Actually the first two statements inside second `for loop` are unnecessary. Because `j` starts from i + 1, so in the first `for loop` you already check the candidate.

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