3Sum
MediumTwo Pointers
Given an integer array nums, return all unique triplets of values [a, b, c] such that a + b + c == 0, where a, b and c come from three different indices of nums.
- The same value may appear more than once in a triplet if it occurs at more than one index (e.g.
[-1, -1, 2]needs two-1s innums). - Two triplets count as duplicates if they contain the same values, regardless of order. Report each distinct triplet only once.
- The triplets, and the values inside each triplet, may be returned in any order.
Return an empty list if no triplet sums to zero.
Example 1
- Input:
- nums = [3,-2,1,0,-1,-1,2]
- Output:
- [[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
- Explanation
- Four different sets of values add to 0.
[-1,-1,2]is valid because-1appears at two different indices.
Example 2
- Input:
- nums = [5,-5,5,0,0]
- Output:
- [[-5,0,5]]
- Explanation
- There are several index choices for -5 + 0 + 5 (two 5s, two 0s), but they all form the same triplet, so it appears once.
Example 3
- Input:
- nums = [1,2,-4]
- Output:
- []
- Explanation
- The only possible triplet is 1 + 2 + (-4) = -1, which is not 0.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5