# [LeetCode] 259. 3Sum Smaller 三数之和较小值

2021年09月15日 阅读数：3

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`.html

For example, given nums = `[-2, 0, 1, 3]`, and target = 2.java

Return 2. Because there are two triplets which sums are less than 2:python

```[-2, 0, 1]
[-2, 0, 3]
```

Could you solve it in O(n2) runtime?数组

Java:指针

```public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if(nums == null || nums.length == 0)
return 0;
Arrays.sort(nums);
int count = 0;

for(int i = 0; i < nums.length - 2; i++) {
int lo = i + 1, hi = nums.length - 1;
while(lo < hi) {
if(nums[i] + nums[lo] + nums[hi] < target) {
count += hi - lo;
lo++;
} else {
hi--;
}
}
}

return count;
}
}　```

Python:code

```# Time:  O(n^2)
# Space: O(1)
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer}
def threeSumSmaller(self, nums, target):
nums.sort()
n = len(nums)

count, k = 0, 2
while k < n:
i, j = 0, k - 1
while i < j:  # Two Pointers, linear time.
if nums[i] + nums[j] + nums[k] >= target:
j -= 1
else:
count += j - i
i += 1
k += 1

return count　　```

C++:htm

```class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
if (nums.size() < 3) return 0;
int res = 0, n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
res += right - left;
++left;
} else {
--right;
}
}
}
return res;
}
};
```

[LeetCode] 15. 3Sum 三数之和

[LeetCode] 16. 3Sum Closest 最近三数之和