3用C ++求和
假设我们有n个称为nums的整数数组,并且还有一个目标,我们必须找到索引三元组(i,j,k)的数量,这里i,j,k都在0到n-1的范围内,并且满足条件nums[i]+nums[j]+nums[k]<目标。
因此,如果输入类似nums=[-2,0,1,3],target=2,则输出将为2,因为有两个三元组的总和小于2:[-2,0,1]和[-2,0,3]。
为了解决这个问题,我们将遵循以下步骤-
ret:=0
对数组进行排序
n:=一个的大小
对于初始化i:=0,当i<n-2时,更新(将i增加1),请执行-
总和:=a[i]+a[left]+a[right]
如果sum<t,则-
除此以外
ret:=ret+右-左
(向左增加1)
(右移1)
左:=i+1,右:=n-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