Problem Statement
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.
Approach
Sort the array. For each element, use two pointers to find pairs that sum to its negation. Skip duplicates.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) excluding output |
Examples
Example 1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2
Input: nums = [0,1,1]
Output: []
Explanation: No three elements sum to zero
Example 3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: One valid triplet
Constraints
- ▸
3 <= nums.length <= 3000 - ▸
-10^5 <= nums[i] <= 10^5
Loading...
Sign in to run your code...
Asked by companies:
FacebookAmazonMicrosoftAppleGoogle