| 14 | */ |
| 15 | public class Solution { |
| 16 | public List<List<Integer>> threeSum(int[] nums) { |
| 17 | List<List<Integer>> list = new ArrayList<>(); |
| 18 | int len = nums.length; |
| 19 | if (len < 3) return list; |
| 20 | Arrays.sort(nums); |
| 21 | int max = nums[len - 1]; |
| 22 | if (max < 0) return list; |
| 23 | for (int i = 0; i < len - 2; ) { |
| 24 | if (nums[i] > 0) break; |
| 25 | if (nums[i] + 2 * max < 0) { |
| 26 | while (nums[i] == nums[++i] && i < len - 2) ; |
| 27 | continue; |
| 28 | } |
| 29 | int left = i + 1, right = len - 1; |
| 30 | while (left < right) { |
| 31 | int sum = nums[i] + nums[left] + nums[right]; |
| 32 | if (sum == 0) { |
| 33 | list.add(Arrays.asList(nums[i], nums[left], nums[right])); |
| 34 | while (nums[left] == nums[++left] && left < right) ; |
| 35 | while (nums[right] == nums[--right] && left < right) ; |
| 36 | } else if (sum < 0) ++left; |
| 37 | else --right; |
| 38 | } |
| 39 | while (nums[i] == nums[++i] && i < len - 2) ; |
| 40 | } |
| 41 | return list; |
| 42 | } |
| 43 | |
| 44 | public static void main(String[] args) { |
| 45 | Solution solution = new Solution(); |