# My easy java solution with explaination [ beating 79.87% of javasubmission]

• ``````The basic idea is to **skip some numbers that are too small or too big for the target**
Assume len = nums.length();
we say nums[i] is "**too small**" if and only if it satisfies nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target; and by skip the small numbers we get an index "start";
Similarly, we say nums[j] is "too big" if and only if num[j] + nums[start] + nums[start+1] + nums[start+2] > target. Then we get another index "end".
Then we can search nums[start: end] by brute force.

PS: the method can be applied to solve "3sum". my submission for "3sum" is accepted but only beats 17% of java submissions.
``````

'''
import java.util.ArrayList;
import java.util.List;

public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new LinkedList<List<Integer>>();
int len = nums.length;

``````	if( len < 4){
return ans;
}

sort(nums,len);

//To skip some small numbers
int start = 0;
for(int i = 0; i < len-3; i++){
if( nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target){
start = i;
}
}

//To skip some big numbers
int end = len - 1;
for(int j = len - 1; j > 2; j--){
if( nums[j] + nums[start] + nums[start+1] + nums[start+2] > target){
end = j;
}else{
break;
}
}

int min1 = Integer.MIN_VALUE;

for( int i = start; i <= end-3; i++){//for-1

/**/for( ; i <= end-3 && nums[i] == min1 ;){i++;} //To skip

int min2 = Integer.MIN_VALUE;
for( int j = i + 1; j <= end-2; j++){//for-2

/**/for( ; j <= end-2 && nums[j] == min2;){j++;} //To skip

int min3 = Integer.MIN_VALUE;
for(int k = j + 1; k <= end-1; k++){//for-3

/**/for(; k <= end-1 && nums[k]== min3 ;){k++;}//To skip

for( int p = k + 1; p <=end; p++){//for-4
int sum = nums[i] + nums[j] + nums[k] + nums[p];
if( sum == target){
List<Integer> tem = new ArrayList<Integer>();
break;
}else if( sum > target){
break;
}//if
}//for-4
min3 = nums[k];
}//for-3
min2 = nums[j];
}//for-2
min1 = nums[i];
}//for-1
return ans;
}

public void sort(int []nums, int len){
for(int i = 0; i < len; i++){
int insertpos = i;
for(int j = i - 1; j >=0; j--){
if(nums[i] < nums[j]){
insertpos = j;
}else{
break;
}
}

int tem = nums[i];
for( int j = i; j > insertpos; j--){
nums[j] = nums[j-1];
}
nums[insertpos] = tem;
}
}
``````

}
'''

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