|
5 | 5 | importjava.util.List; |
6 | 6 |
|
7 | 7 | publicclass_3Sum { |
8 | | - |
| 8 | +/**This solution is pretty clear and similar to my own thought: |
| 9 | + * https://discuss.leetcode.com/topic/26050/simple-o-n-2-two-pointers-java-solution*/ |
| 10 | + |
| 11 | +/**ATTN: this two-pointer technique here doesn't need a middle pointer!!! Instead, we just increment/decrement left |
| 12 | + * or right pointer by 1 each time when the sum != 0*/ |
9 | 13 | publicList<List<Integer>>threeSum(int[]nums) { |
10 | | -Arrays.sort(nums); |
11 | 14 | List<List<Integer>>result =newArrayList(); |
12 | | -intleft =0,right =nums.length-1,mid =0; |
13 | | -while(left+1 <right){ |
14 | | -mid =left + (right-left)/2; |
15 | | -intsum =nums[left] +nums[mid] +nums[right]; |
16 | | -if(sum ==0){ |
17 | | -List<Integer>list =newArrayList(); |
18 | | -list.add(nums[left]); |
19 | | -list.add(nums[mid]); |
20 | | -list.add(nums[right]); |
21 | | - |
22 | | -//move left forward to get all possible combinations |
23 | | - }elseif(sum >0){ |
24 | | -right =mid; |
25 | | - }else { |
26 | | -left =mid; |
| 15 | +if(nums ==null ||nums.length ==0)returnresult; |
| 16 | +Arrays.sort(nums);//you'll have to sort it first, this is very important and very natural to think of |
| 17 | +for(inti =0;i <nums.length;i++){//we can let i reach the last element, it's fine since we have other checks afterwards, it won't go out of bound exception. |
| 18 | +if(i >=1 &&nums[i] ==nums[i-1])continue;//skip equal elements to avoid duplicates |
| 19 | +intleft =i+1,right =nums.length-1; |
| 20 | +while(left <right){ |
| 21 | +intsum =nums[i] +nums[left] +nums[right]; |
| 22 | +if(sum ==0){ |
| 23 | +result.add(Arrays.asList(nums[i],nums[left],nums[right])); |
| 24 | +while(left +1 <right &&nums[left] ==nums[left+1])left++; |
| 25 | +while(right -1 >left &&nums[right] ==nums[right-1])right--; |
| 26 | +left++;//be sure to have these two lines after the above two while loops |
| 27 | +right--; |
| 28 | + }elseif(sum <0){ |
| 29 | +left++; |
| 30 | + }else { |
| 31 | +right--; |
| 32 | + } |
27 | 33 | } |
28 | 34 | } |
| 35 | +returnresult; |
29 | 36 | } |
30 | 37 |
|
31 | 38 | } |