|
题目：
Given an array of n integers nums and a 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:
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?
这道题是要求一个数组中任意三个数字相加之和小于target的个数。我差一点点就做出来了，哎。就还是3sum的套路，固定外层，里面用双指针解决。在双指针判断的大小的过程中需要有一点变化，那就是如果sum < target的话，因为是按升序排序的，所以相当于再固定start的话后面加任意从start+1开始一直到end的数字都是满足条件的，于是result就可以直接+= (end - start)，同时也需要再把start往后挪一个，其实跟3sum就是一样的了，但是刚开始想岔了以为可以直接break掉orz……其他情况下就直接往前挪end就好。时间复杂度O(n^2)，空间O(1)。
Runtime: 6 ms, faster than 42.67% of Java online submissions for 3Sum Smaller.
Memory Usage: 38.5 MB, less than 47.06% of Java online submissions for 3Sum Smaller.
class Solution {
public int threeSumSmaller(int[] nums, int target) {
int result = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int pStart = i + 1;
int pEnd = nums.length - 1;
while (pStart < pEnd) {
int sum = nums[i] + nums[pStart] + nums[pEnd];
if (sum < target) {
result += (pEnd - pStart);
pStart++;
} else {
pEnd--;
}
}
}
return result;
}
}
| 
转播
