Permalink
Sep 3, 2021
Newer
100644
55 lines (49 sloc)
1.55 KB
1
/**
2
*
3
* Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
4
*
5
Example 1:
6
Input: [-3, 0, 1, 2, -1, 1, -2]
7
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]
8
Explanation: There are four unique triplets whose sum is equal to zero.
9
10
Example 2:
11
Input: [-5, 2, -1, -2, 3]
12
Output: [[-5, 2, 3], [-2, -1, 3]]
13
Explanation: There are two unique triplets whose sum is equal to zero.
14
*
15
*/
16
17
function tripletSumToZero (inputArr){
18
var result = []
19
var input = inputArr.sort()
20
for (var i = 0; i < input.length; i++){
21
if(i > 0 && input[i] === input[i-1])
22
continue
23
findTriplet(input, i+1, -input[i], result)
24
}
25
return result
26
}
27
28
function findTriplet(input, left, target, result){
29
var right = input.length - 1
30
31
while(right > left){
32
var sum = input[left] + input[right]
33
if (sum === target){
34
result.push([-sum, input[left], input[right]])
35
left += 1
36
right -= 1
37
while(right > left && input[left] === input[left - 1]){
38
left += 1
39
}
40
while(right > left && input[right] === input[right - 1]){
41
right -= 1
42
}
43
}else if (sum > target){
44
right -= 1
45
}else {
46
left += 1
47
}
48
}
49
}
50
51
let input = [-3, 0, 1, 2, -1, 1, -2]
52
let input1 = [-5, 2, -1, -2, 3]
53
54
console.log(`The unique triplets that add up to zero for ${[input]} is`, tripletSumToZero(input))
55
console.log(`The unique triplets that add up to zero for ${[input1]} is`, tripletSumToZero(input1))