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)