259 3Sum Smaller
259. 3Sum Smaller
1. Question
Given an array ofnintegersnumsand atarget, find the number of index tripletsi, j, k
with0 <= i < j < k < n
that 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:
[-2, 0, 1]
[-2, 0, 3]
Follow up: Could you solve it inO(n^2) runtime?
2. Implementation
(1) Two Pointers
class Solution {
public int threeSumSmaller(int[] nums, int target) {
int res = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int j = i + 1, k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum < target) {
res += k - j;
++j;
}
else {
--k;
}
}
}
return res;
}
}
3. Time & Space Complexity
时间复杂度O(n^2), 空间复杂度O(1)
Last updated
Was this helpful?