C++ 中的 3Sum Smaller
c++server side programmingprogramming
假设我们有一个名为 nums 的 n 个整数数组,并且我们还有一个目标,我们必须找到索引三元组 (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)
return ret
Example
让我们看看下面的实现以便更好地理解 −
#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