Description Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example 1 2 3 4 5 6 7 Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Solution 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 class Solution { public List<List<Integer>> threeSum(int [] nums) { List<List<Integer>> res = new ArrayList<>(); if (nums == null || nums.length == 0 ) return res; Arrays.sort(nums); for (int i = 0 ; i < nums.length - 2 ; i ++){ if (i > 0 && nums[i] == nums[i-1 ]) continue ; if (nums[i] > 0 ) break ; int j = i + 1 ; int k = nums.length-1 ; while (j < k){ if (nums[i] + nums[j] + nums[k] == 0 ){ List<Integer> tmp = new ArrayList<>(); tmp.add(nums[i]); tmp.add(nums[j]); tmp.add(nums[k]); res.add(tmp); j++; while (j < k && nums[j] == nums[j-1 ]) j++; k--; while (j < k && nums[k] == nums[k+1 ]) k--; } else if (nums[i] + nums[j] + nums[k] < 0 ){ j++; while (j < k && nums[j] == nums[j-1 ]) j++; } else if (nums[i] + nums[j] + nums[k] > 0 ){ k--; while (j < k && nums[k] == nums[k+1 ]) k--; } } } return res; } }
Time Complex: $O(N^2)$