题目地址：https://leetcode-cn.com/problems/3sum-smaller/
题目描述
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?
题目大意
给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
解题方法
二分查找
先对数组进行排序。
固定i, j找出k，使得nums[k] >= target - nums[i] - nums[j]。 此时满足nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数是 k - j - 1个。
- lower_bound()找出A[i] >`= target的i
- upper_bound()找出A[i] >` target的i
所以使用lower_bound()找出大于等于target - nums[i] - nums[j]的k位置，此位置的k是第一个不满足题设的位置。因此满足条件的k在左边，共有k - j - 1个。
另外二分查找的时候，并不是从头开始查找，而是从nums.begin() + j + 1查找，即j的下一个元素位置开始。
时间复杂度O(N^2 * log(N)).
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
双指针
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++;
时间复杂度O(N^2).
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发