The question
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
The idea
- Array must be sorted.
- Iterate through the list + Left and right pointer.
- Result must be a set because they may be duplicate values.
- Order of the tuple (current value, left pointer, right pointer) inserted into result matters.
Python
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: result = set() nums.sort() for i in range(len(nums) - 2): currentValue = nums[i] left = i + 1 right = len(nums) - 1 while left < right: totalSum = currentValue + nums[left] + nums[right] if totalSum > 0: right -= 1 // if there is no negative value, left += 1 will only increase totalSum elif totalSum < 0: left += 1 else: result.add((currentValue, nums[left], nums[right])) left += 1 right -= 1 return result
Java
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); Set<List<Integer>> set = new HashSet<>(); for (int i = 0; i<nums.length - 2; i++) { int currentValue = nums[i]; int start = i + 1; int end = nums.length - 1; while (start < end) { int total = currentValue + nums[start] + nums[end]; if (total < 0) { start += 1; } else if (total > 0) { end -= 1; } else { set.add(Arrays.asList(currentValue, nums[start], nums[end])); start += 1; end -= 1; } } } return new ArrayList<>(set); } }
Top comments (0)