# 259. 3Sum Smaller 较小的三数之和

@TOC

## # 题目描述

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?

## # 解题方法

### # 二分查找

• `lower_bound()`找出`A[i] >= target``i`
• `upper_bound()`找出`A[i] > target``i`

C++代码如下：

``````class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
const int N = nums.size();
if (N <= 2) return 0;
sort(nums.begin(), nums.end());
int res = 0;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
int numsk = target - nums[i] - nums[j];
int k = lower_bound(nums.begin() + j + 1, nums.end(), numsk) - nums.begin();
res += k - j - 1;
}
}
return res;
}
};
``````

### # 双指针

`j`指向起始，`k`指向结束，找到`nums[j] + nums[k] < target - nums[i]`的区间长度，里面的元素全都符合。

• 如果`nums[j] + nums[k] >= target - nums[i]`，说明k太大，需要k--;
• 如果`nums[j] + nums[k] < target - nums[i]`，说明满足条件，又由于j比较小，需要j++;

C++代码如下：

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

## # 日期

2019 年 9 月 22 日 —— 熬夜废掉半条命