0259. 3Sum Smaller
https://leetcode.com/problems/3sum-smaller
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
ac
// n sum, two pointers, opposite direction
class Solution {
public int threeSumSmaller(int[] nums, int target) {
// sort
// walk one pass. index i, l, r, i < nums.length - 2
// while i+l+r >= target, r--. -> add to result, r - l.
// l++, while i+l+r >= target, r--
// edge cases
if (nums.length < 3) return 0;
// init
int res = 0;
Arrays.sort(nums);
// loop
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1, r = nums.length - 1;
while (l < r) {
while (l < r && nums[i] + nums[l] + nums[r] >= target) r--;
if (l == r) break;
res += r - l;
l++;
}
}
return res;
}
}
Last updated
Was this helpful?