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