3Sum Smaller - Đếm triplet tổng nhỏ hơn target

Cho mảng nums và target. Đếm số triplet (i,j,k) (inums[i]+nums[j]+nums[k] < target.

Ví dụ: [-2,0,1,3], target=2 → 2 triplet: [-2,0,1], [-2,0,3].

Giải thuật (Sort + Hai con trỏ)

Sắp xếp mảng. Với mỗi i, đặt left=i+1, right=n-1. Nếu tổng < target, mọi cặp giữa left và right đều hợp lệ → cộng right-left, tăng left. Ngược lại giảm right.

Cài đặt C++

#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, 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-2,0,1,3};
    cout << ob.threeSumSmaller(v, 2);
    return 0;
}

Đầu vào

[-2,0,1,3] 2

Đầu ra

2