|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Arrays; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +publicclass_4Sum { |
| 8 | +/**Then I went online and found that there're really smarter/more efficient solutions out there: |
| 9 | + * Post 1: https://discuss.leetcode.com/topic/29585/7ms-java-code-win-over-100 |
| 10 | + * this post basically uses two subfunctions, it keeps using binary search to divide this 4sum to 3sum and then to 2sum, |
| 11 | + * thus, it's really fast!!!! Instead of using two for loops.*/ |
| 12 | + |
| 13 | +/**My original solution:*/ |
| 14 | + |
| 15 | + |
| 16 | +publicList<List<Integer>>fourSum(int[]nums,inttarget) { |
| 17 | +List<List<Integer>>result =newArrayList(); |
| 18 | +if(nums ==null ||nums.length ==0)returnresult; |
| 19 | +Arrays.sort(nums); |
| 20 | +for(inti =0;i <nums.length -3;i++){ |
| 21 | +if(i >0 &&nums[i-1] ==nums[i])continue; |
| 22 | +for(intj =i+1;j <nums.length-2;j++){ |
| 23 | +if(j >i+1 &&nums[j-1] ==nums[j])continue; |
| 24 | +intleft =j+1,right =nums.length-1; |
| 25 | +while(left <right){ |
| 26 | +intsum =nums[i] +nums[j] +nums[left] +nums[right]; |
| 27 | +if(sum ==target){ |
| 28 | +result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); |
| 29 | +while(left+1 <right &&nums[left] ==nums[left+1])left++; |
| 30 | +while(right-1 >left &&nums[right] ==nums[right-1])right--; |
| 31 | +left++; |
| 32 | +right--; |
| 33 | + }elseif(sum >target)right--; |
| 34 | +elseleft++; |
| 35 | + } |
| 36 | + } |
| 37 | + } |
| 38 | +returnresult; |
| 39 | + } |
| 40 | + |
| 41 | +} |