3C++에서 더 작은 합

<시간/>

nums라고 하는 n개의 정수 배열이 있고 목표도 있다고 가정하고 여기에서 인덱스 삼중항(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
배열 정렬 a
n :=a
의 크기
initialize i :=0의 경우 i
- 왼쪽 :=i + 1, 오른쪽 :=n - 1
- 왼쪽 <오른쪽 동안 −
  - 합계 :=a[i] + a[왼쪽] + a[오른쪽]
  - 합계
    - ret :=ret + 오른쪽 - 왼쪽
    - (왼쪽으로 1씩 증가)
  - 그렇지 않으면
    - (오른쪽으로 1 감소)
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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