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

相关文章