Array
Two Pointers
Binary Search
Sorting
Description
Given an array of n
integers nums
and an integer target
, find the number of index triplets i
, j
, k
with 0 <= i < j < k < n
that satisfy the condition nums[i] + nums[j] + nums[k] < target
.
Example 1:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]
Example 2:
Input: nums = [], target = 0
Output: 0
Example 3:
Input: nums = [0], target = 0
Output: 0
Constraints:
n == nums.length
0 <= n <= 3500
-100 <= nums[i] <= 100
-100 <= target <= 100
Solutions
Solution 1
Python3 Java C++ Go JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def threeSumSmaller ( self , nums : List [ int ], target : int ) -> int :
nums . sort ()
ans , n = 0 , len ( nums )
for i in range ( n ):
j , k = i + 1 , n - 1
while j < k :
s = nums [ i ] + nums [ j ] + nums [ k ]
if s >= target :
k -= 1
else :
ans += k - j
j += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public int threeSumSmaller ( int [] nums , int target ) {
Arrays . sort ( nums );
int ans = 0 ;
for ( int i = 0 , n = nums . length ; i < n ; ++ i ) {
int j = i + 1 ;
int k = n - 1 ;
while ( j < k ) {
int s = nums [ i ] + nums [ j ] + nums [ k ] ;
if ( s >= target ) {
-- k ;
} else {
ans += k - j ;
++ j ;
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
int threeSumSmaller ( vector < int >& nums , int target ) {
sort ( nums . begin (), nums . end ());
int ans = 0 ;
for ( int i = 0 , n = nums . size (); i < n ; ++ i ) {
int j = i + 1 , k = n - 1 ;
while ( j < k ) {
int s = nums [ i ] + nums [ j ] + nums [ k ];
if ( s >= target )
-- k ;
else {
ans += k - j ;
++ j ;
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func threeSumSmaller ( nums [] int , target int ) int {
sort . Ints ( nums )
ans := 0
for i , n := 0 , len ( nums ); i < n ; i ++ {
j , k := i + 1 , n - 1
for j < k {
s := nums [ i ] + nums [ j ] + nums [ k ]
if s >= target {
k --
} else {
ans += k - j
j ++
}
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumSmaller = function ( nums , target ) {
nums . sort (( a , b ) => a - b );
let ans = 0 ;
for ( let i = 0 , n = nums . length ; i < n ; ++ i ) {
let j = i + 1 ;
let k = n - 1 ;
while ( j < k ) {
s = nums [ i ] + nums [ j ] + nums [ k ];
if ( s >= target ) {
-- k ;
} else {
ans += k - j ;
++ j ;
}
}
}
return ans ;
};