Permalink
Sep 4, 2021
Newer
100644
46 lines (39 sloc)
1.23 KB
1
/**
2
*
3
* Given an array arr of unsorted numbers and a target sum, count all triplets in it
4
* such that arr[i] + arr[j] + arr[k] < target where i, j, and k are three different indices.
5
* Write a function to return the count of such triplets.
6
*
7
8
Example 1:
9
Input: [-1, 0, 2, 3], target=3
10
Output: 2
11
Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2]
12
13
Example 2:
14
Input: [-1, 4, 2, 1, 3], target=5
15
Output: 4
16
Explanation: There are four triplets whose sum is less than the target:
17
[-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]
18
19
*
20
*/
21
22
function tripletWithSmallerSum(inputArr, target){
23
var input = inputArr.sort()
24
var count = 0
25
26
for(let i = 0; i < input.length - 2; i++){
27
let left = i+1
28
let right = input.length - 1
29
while(right > left) {
30
let sum = input[i] + input[left] + input[right]
31
if(sum >= target){
32
right -= 1
33
}else {
34
count += right - left
35
left += 1
36
}
37
}
38
}
39
return count
40
}
41
42
let input = [-1, 0, 2, 3], target=3
43
let input1 = [-1, 4, 2, 1, 3], target1=5
44
45
console.log(tripletWithSmallerSum(input, target))
46
console.log(tripletWithSmallerSum(input1, target1))