15. 3Sum
## description
## 15. 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.
Example 1:
1Input: nums = [-1,0,1,2,-1,-4]
2Output: [[-1,-1,2],[-1,0,1]]
3Explanation:
4nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
5nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
6nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
7The distinct triplets are [-1,0,1] and [-1,-1,2].
8Notice that the order of the output and the order of the triplets does not matter.Example 2:
1Input: nums = [0,1,1]
2Output: []
3Explanation: The only possible triplet does not sum up to 0.Example 3:
1Input: nums = [0,0,0]
2Output: [[0,0,0]]
3Explanation: The only possible triplet sums up to 0.- –3 <= nums.length <= 3000
- –-105 <= nums[i] <= 105
Constraints:
## notes
### Intuition
Building on the two-pointer approach from Two Sum II, we can fix one number and use two pointers on the remaining sorted array to find pairs that sum to its negation. Sorting enables efficient duplicate skipping.
### Implementation
Sort the array first. For each number nums[i], set up left and right pointers on the subarray to its right. If l + r equals the target (negation of nums[i]), we found a triplet. If the sum is too large, move right inward; if too small, move left outward. Continue searching even after finding a triplet.
### Edge-cases
Duplicates require careful handling. Skip duplicate values of nums[i] at the outer loop level. After finding a triplet, advance both l and r past any duplicates to avoid adding the same triplet multiple times.
- –Time: O(n²) — sorting is O(n log n), nested iteration is O(n²)
- –Space: O(1) — excluding the output array
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def threeSum(self, nums: List[int]) -> List[List[int]]:
5 nums = sorted(nums)
6 print(f"nums = {nums}")
7 i = 0
8 ans = []
9 # To have at least 3 elements
10 for i in range(len(nums)):
11 if i > 0 and nums[i] == nums[i - 1]:
12 continue
13
14 target = nums[i] * -1
15 l, r = i + 1, len(nums) - 1
16 while l < r:
17 potential = nums[l] + nums[r]
18 if potential == target:
19 ans.append([nums[i], nums[l], nums[r]])
20 while l < r and nums[l] == nums[l + 1]:
21 l += 1
22 while l < r and nums[r] == nums[r - 1]:
23 r += 1
24 l += 1
25 r -= 1
26 elif potential < target:
27 l += 1
28 else:
29 r -= 1
30 return ans
31
32
33
34
35if __name__ == "__main__":
36 # Include one-off tests here or debugging logic that can be run by running this file
37 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
38 solution = Solution()
39