Time O(n2) & Memory O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | class Solution { public List < List < Integer >> threeSum(int[] nums) { int n = nums.length; List < List < Integer >> list = new ArrayList < List < Integer >> (); if(nums == null || nums.length<3) return list; Arrays.sort(nums); int left, right; for (int i = 0; i < n - 2; i++) { if(i > 0 && nums[i] == nums[i-1]) continue; left = i + 1; right = n - 1; while (left < right) { if (nums[left] + nums[right] + nums[i] == 0) { List < Integer > temp = new ArrayList < Integer > (); temp.add(nums[i]); temp.add(nums[left]); temp.add(nums[right]); list.add(temp); left++; right--; while (left< right && nums[left] == nums[left - 1]) { left++; } while (left< right && nums[right] == nums[right + 1]) { right--; } } else if (nums[left] + nums[right] + nums[i] > 0) { right--; } else left++; } } return list; } } |