05 August 2008
Given an array of n integers nums and a target, find the number of index triplets 1
i, j, k
1
0 <= i < j < k < n
1
nums[i] + nums[j] + nums[k] < target
Example:
1
2
3
4
5
Input: nums = [-2,0,1,3], and target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]
Follow up: Could you solve it in O(n2) runtime?
这个题完全是3Sum的略微变化，维持一个变量counter记录排序后小于target的triplets的数量即可。
Time: O(nlogn) + O(n^2) = O(n^2); Space: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}
int count = 0;
Arrays.sort(nums);//因为只用返回小于target的triplets的个数，所以顺序没关系，不用单独记住原数组的indices
for (int first = 0; first <= nums.length - 3; first++) {
int second = first + 1, third = nums.length - 1;
while (second < third) {
int sum = nums[first] + nums[second] + nums[third];
if (sum < target) {
count += third - second;//这里的意思是排序后只要三个数相加小于target，那么third之前的数肯定也和first，second相加小于target
second++;//上面加完后，右移第二个index再进行同样的确认；如果second后面的数是一样的呢，可否优化？
} else {
third--;//大于或等于的话，把第三个index左移，缩小范围；如果third前面的数是一样的呢，可否优化？
}
}
}
return count;
}
}