โปรแกรมนับ Triplet ที่ผลรวมน้อยกว่า Target (Python)

ปัญหา

กำหนด list nums และ target นับจำนวน triplet (i < j < k) ที่ nums[i] + nums[j] + nums[k] < target

ตัวอย่าง: nums=[-2,6,4,3,8], target=12 → 5 triplets
[-2,6,4], [-2,6,3], [-2,4,3], [-2,4,8], [-2,3,8]

วิธีแก้: Sort + Two Pointers (Counting)

อัลกอริทึม

1. Sort nums
2. ans = 0
3. วน i = 0 ถึง n-1:
   • k = n-1
   • วน j = i+1 ถึง n-1:
     • While k > j และ nums[i] + nums[j] + nums[k] ≥ target: k--
     • ถ้า j == k: break
     • ans += k - j (ทุก index ระหว่าง j+1 ถึง k ให้ sum < target)

โค้ด Python

class Solution:
    def solve(self, nums, target):
        nums.sort()
        ans = 0
        n = len(nums)
        
        for i in range(n):
            k = n - 1
            for j in range(i + 1, n):
                while k > j and nums[i] + nums[j] + nums[k] >= target:
                    k -= 1
                if j == k:
                    break
                ans += k - j
        
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve([-2, 6, 4, 3, 8], 12))  # 5
print(ob.solve([1, 2, 3, 4, 5], 10))   # 4 (1,2,3), (1,2,4), (1,2,5), (1,3,4)
print(ob.solve([0, 0, 0, 0], 1))       # 4 (all combinations)

ความซับซ้อน

• Time: O(n²) - outer loop n, inner loop n, k pointer รวม O(n)
• Space: O(1) หรือ O(log n) สำหรับ sort

เหตุผลที่ k - j ให้จำนวน triplet

เมื่อ nums[i] + nums[j] + nums[k] < target และ array เรียงแล้ว
→ สำหรับ j นี้ fixed, ทุก index m ที่ j < m ≤ k จะได้ sum < target (เพราะ nums[m] ≤ nums[k])
→ จำนวน = k - j

LeetCode 259: 3Sum Smaller

นี่คือโจทย์ "3Sum Smaller" - นับแทนการหา triplet จริง