数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中的 3Sum Smaller
假设我们有一个名为 nums 的包含 n 个整数的数组，我们还有一个目标值 target，我们需要找到索引三元组 (i, j, k) 的数量，其中 i、j、k 的范围都在 0 到 n - 1 之间，并且满足条件 nums[i] + nums[j] + nums[k] < target。
因此，如果输入类似于 nums = [-2,0,1,3]，而 target = 2，则输出将为 2，因为有两个三元组的和小于 2：[-2,0,1] 和 [-2,0,3]。
为了解决这个问题，我们将遵循以下步骤：
ret := 0
对数组 a 进行排序
n := a 的大小
对于初始化 i := 0，当 i < n - 2 时，更新（将 i 增加 1），执行：
left := i + 1, right := n - 1
当 left < right 时，执行：
sum := a[i] + a[left] + a[right]
如果 sum < t，则：
ret := ret + right - left
(将 left 增加 1)
否则
(将 right 减小 1)
返回 ret
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumSmaller(vector<int<& a, int t) {
int ret = 0;
sort(a.begin(), a.end());
int n = a.size();
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum < t) {
ret += right - left;
left++;
}
else
right--;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int< v = {-2,0,1,3};
cout << (ob.threeSumSmaller(v,2));
}输入
[-2,0,1,3] 2
输出
2
更新于：2020-11-18
265 次浏览
广告