Given an array of integers, determine if there exists a triple [nums[i], nums[j], nums[k]] that satisfies i ! = j, i ! = k and j ! = k and also satisfies nums[i] + nums[j] + nums[k] == 0. Return all triples that sum to 0 and are not duplicates.
Note: Answers may not contain duplicate triples.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
The different triples are [-1,0,1] and [-1,-1,2].
Note that the order of the output and the order of the triples do not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: the only possible ternary sum is not 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible ternary sum is 0.
Tip:
3 <= <= 3000
-105 <= nums[i] <= 105
Thought Analysis.
In solving the "sum of three numbers" problem, the process of analysis and derivation of ideas is as follows:
- Requirements and analysis of the problem
The question asks to find three numbers that sum to zero and needs to output all non-repeating triples. Arrays may contain positive numbers, negative numbers, and zero, so the ternary found may consist of a combination of positive and negative numbers.
Input characteristics: there is no specific pattern to the numbers in the array, they may be positive, negative, or zero.
Output requirement: non-repeating triples that sum to zero.
The simplest and most direct way to think about it is by solving it violently, ie:
For each element in the array, iterate through all possible combinations to find a ternary that matches the condition.
The time complexity of the violent solution is O(n³), which does not satisfy the requirements of the topic.
- From violent solutions to optimization
In brute-force solving, after determining one number, finding the remaining two numbers can be viewed as a "sum-of-two" problem. If we can find the remaining two numbers quickly in some way, we can reduce the complexity of the traversal.
The common problem of sum of two numbers can be realized by a hash table, but the key point here is that we need to find the ternary not only to sum to zero, but also need to make sure that it is not duplicated, which increases the difficulty of the search. - Introducing sorting and double pointers
To reduce the lookup complexity, we can first sort the array. Sorting has two benefits:
1. Sort the array to make it easy to quickly find the remaining two numbers using the double pointer technique.
2. Sorting can help remove duplicate solutions (because the same elements need to be considered only once).
-
Fix a number: traverse the array and fix one of the numbers nums[i].
Finding the remaining two numbers: find the other two numbers in the remaining part of the array whose sum is -nums[i] by the double pointer trick.
- Use of double pointers
The two-pointer trick is a way of using two pointers (usually head and tail) to perform a lookup in an ordered array.
Suppose we fixed nums[i] and need to find two numbers nums[left] and nums[right] in the remaining array such that their sum is -nums[i].
By the nature of double pointers:
If the sum of the current three numbers, nums[i] + nums[left] + nums[right], is less than zero, we need a bigger number, so the left pointer, left, is moved to the right.
If the current sum of the three numbers is greater than zero, that means we need a smaller number, so the right pointer right is shifted left.
If the sum of the three numbers is found to be zero, the result is saved and the two pointers are moved simultaneously to continue the search for other possible combinations.
- The problem of de-duplication
Due to the possibility of duplicate elements, the result cannot contain duplicate triples. Therefore, de-duplication needs to be specifically handled in the implementation:
When traversing, if the current element is the same as the previous one, it is skipped directly to avoid repeated calculations.
After finding a triple that matches the conditions, you need to skip the elements of the array that are the same as the current left and right pointers, to make sure you don't process the same combinations over and over again.
-
Why choose double pointers?
Time Complexity Optimization: The double pointer method reduces the complexity of the brute force solution from O(n³) to O(n²) due to the fact that each time the outer loop fixes a number, the rest of the part can be done by just one double pointer lookup.
Benefits of sorting: Although sorting takes O(n log n) time, the double pointer method can effectively use the ordering of the array to quickly adjust the lookup range in the sorted array, which optimizes the overall complexity. -
Summarizing thoughts
The final thoughts on solving this problem are summarized below:Sorting: The array is first sorted to facilitate subsequent search and de-duplication.
Iterate through the array: for each nums[i], reduce the problem to finding two numbers in the remaining array that make the sum of the three numbers zero.
Double pointer lookup: Use double pointer lookup in ordered arrays to resize the sum by moving the pointer.
De-duplication: ensures that the result set does not contain duplicate triples and handles duplicate elements in the traversal.
Click to view code
func threeSum(nums []int) [][]int {
(nums)
var res [][]int
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue // de-emphasize
}
left, right := i + 1, len(nums) - 1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
// Skip the repetitive left cap (a poem) right
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++ // update left
right-- // update right
} else if sum < 0 {
left++
} else {
right--
}
}
}
return res
}