Giả sử chúng ta có một mảng gồm n số nguyên được gọi là num và chúng ta cũng có một đích, chúng ta phải tìm số bộ ba chỉ số (i, j, k) ở đây i, j, k đều nằm trong phạm vi từ 0 đến n - 1 và đó thỏa mãn điều kiện nums [i] + nums [j] + nums [k]
Vì vậy, nếu đầu vào giống như nums =[-2,0,1,3] và target =2, thì đầu ra sẽ là 2, vì có hai bộ ba có tổng nhỏ hơn 2:[-2,0, 1] và [-2,0,3].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
ret:=0
sắp xếp mảng a
n:=kích thước của một
để khởi tạo i:=0, khi i
left:=i + 1, right:=n - 1
trong khi trái
sum:=a [i] + a [left] + a [right]
nếu sum
ret:=ret + phải - trái
(tăng bên trái 1)
Nếu không
(giảm bên phải 1)
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[-2,0,1,3] 2
Đầu ra
2
