สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม n ตัวที่เรียกว่า nums และเรามีเป้าหมายด้วย เราต้องหาจำนวนของดัชนี triplets (i, j, k) ที่นี่ i, j, k ทั้งหมดอยู่ในช่วง 0 ถึง n - 1 และนั่น เป็นไปตามเงื่อนไข nums[i] + nums[j] + nums[k]
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[-2,0,1,3] และเป้าหมาย =2 ผลลัพธ์จะเป็น 2 เนื่องจากมีแฝดสามตัวที่ผลรวมน้อยกว่า 2:[-2,0, 1] และ [-2,0,3].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ยกเลิก :=0
จัดเรียงอาร์เรย์ a
n :=ขนาดของ a
สำหรับการเริ่มต้น i :=0 เมื่อ i
ซ้าย :=i + 1, ขวา :=n - 1
ขณะที่ซ้าย <ขวา ทำ -
ผลรวม :=a[i] + a[left] + a[right]
ถ้าผลรวม
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
ผลลัพธ์
2
