Two Pointers
09. 3Sum
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.
Notice that the solution set must not contain duplicate triplets.
Examples
Example 1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: The distinct triplets are [-1,0,1] and [-1,-1,2]. Order does not matter.
Example 2
Input: nums = [0,1,1]
Output: []
Explanation: No triplet sums to 0.
Example 3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums to 0.
Constraints
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
from typing import List
nums: List[int] = [-1,0,1,2,-1,-4]
answer: List[List[int]] = []
nums.sort()
for i, v in enumerate(nums):
# Skip duplicate values for the first element
if i > 0 and nums[i] == nums[i-1]:
continue
l: int = i + 1
r: int = len(nums) - 1
while l < r:
three_sum: int = nums[l] + nums[r] + v
if three_sum > 0:
r -= 1
elif three_sum < 0:
l += 1
else:
answer.append([nums[l], nums[r], v])
r -= 1
l += 1
# Skip duplicates for left and right pointers
while l < r and nums[l - 1] == nums[l]:
l += 1
while l < r and nums[r + 1] == nums[r]:
r -= 1
print(answer)Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help