259 3Sum Smaller

259. 3Sum Smaller

1. Question

Given an array ofnintegersnumsand atarget, find the number of index tripletsi, j, kwith0 <= i < j < k < nthat satisfy the conditionnums[i] + nums[j] + nums[k] < target.
For example, givennums=[-2, 0, 1, 3], andtarget= 2.
Return 2. Because there are two triplets which sums are less than 2:
1
[-2, 0, 1]
2
[-2, 0, 3]
Copied!
Follow up: Could you solve it inO(n^2) runtime?

2. Implementation

(1) Two Pointers
1
class Solution {
2
public int threeSumSmaller(int[] nums, int target) {
3
int res = 0;
4
Arrays.sort(nums);
5
6
for (int i = 0; i < nums.length - 2; i++) {
7
int j = i + 1, k = nums.length - 1;
8
9
while (j < k) {
10
int sum = nums[i] + nums[j] + nums[k];
11
12
if (sum < target) {
13
res += k - j;
14
++j;
15
}
16
else {
17
--k;
18
}
19
}
20
}
21
return res;
22
}
23
}
Copied!

3. Time & Space Complexity

时间复杂度O(n^2), 空间复杂度O(1)