3Sum
medium●Arrays & Hashing
The **3Sum** problem asks us to find all unique triplets in an array which give the sum of zero.
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.
### How it works (Sorting + Two Pointers approach): 1. **Sort the array** first. This is crucial as it allows us to use the Two Pointers technique and easily skip duplicate elements. 2. Iterate through the array with an index `i` (the "base" pointer). 3. If `nums[i]` is the same as the previous element `nums[i-1]`, skip it to avoid duplicate triplets. 4. Set two pointers: `left` at `i + 1` and `right` at the end of the array. 5. While `left < right`: - Calculate `sum = nums[i] + nums[left] + nums[right]`. - If `sum == 0`, we found a triplet! Add it to the result, then move both pointers inward, making sure to skip over any duplicate values to avoid duplicate triplets. - If `sum < 0`, the sum is too small. Since the array is sorted, we can increase the sum by moving the `left` pointer to the right. - If `sum > 0`, the sum is too large. We can decrease it by moving the `right` pointer to the left.
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.
### How it works (Sorting + Two Pointers approach): 1. **Sort the array** first. This is crucial as it allows us to use the Two Pointers technique and easily skip duplicate elements. 2. Iterate through the array with an index `i` (the "base" pointer). 3. If `nums[i]` is the same as the previous element `nums[i-1]`, skip it to avoid duplicate triplets. 4. Set two pointers: `left` at `i + 1` and `right` at the end of the array. 5. While `left < right`: - Calculate `sum = nums[i] + nums[left] + nums[right]`. - If `sum == 0`, we found a triplet! Add it to the result, then move both pointers inward, making sure to skip over any duplicate values to avoid duplicate triplets. - If `sum < 0`, the sum is too small. Since the array is sorted, we can increase the sum by moving the `left` pointer to the right. - If `sum > 0`, the sum is too large. We can decrease it by moving the `right` pointer to the left.
Constraints
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
TimeO(O(n²))
SpaceO(O(1) or O(n))
Ready to startStep 0 / 0
TypeScript