โปรแกรมตรวจสอบว่ามี 4 ตัวเลข Unique ผลรวมเท่ากับ k หรือไม่ (Python)

ปัญหา

กำหนด list nums และ target k ตรวจสอบว่ามี 4 ตัวเลข unique ที่ผลรวม = k

ตัวอย่าง: nums=[11,4,6,10,5,1], k=25 → True (4+6+10+5=25)

วิธีแก้: Sort + Nested Loops + Two Pointers (4Sum Existence)

ลดปัญหา 4Sum เป็น 2Sum ด้วย nested loops 2 ระดับ

อัลกอริทึม

1. Sort nums
2. วน i = 0 ถึง n-4:
   • วน j = i+1 ถึง n-3:
     • Two pointers: l = j+1, h = n-1
     • While l < h:
       • sum = nums[i] + nums[j] + nums[l] + nums[h]
       • ถ้า sum == k: return True
       • ถ้า sum < k: l++
       • ถ้า sum > k: h--

โค้ด Python

class Solution:
    def solve(self, nums, k):
        nums.sort()
        n = len(nums)
        
        for i in range(n - 3):
            for j in range(i + 1, n - 2):
                l, h = j + 1, n - 1
                while l < h:
                    summ = nums[i] + nums[j] + nums[l] + nums[h]
                    if summ == k:
                        return True
                    elif summ < k:
                        l += 1
                    else:
                        h -= 1
        return False

# ทดสอบ
ob = Solution()
print(ob.solve([11, 4, 6, 10, 5, 1], 25))  # True (4+6+10+5)
print(ob.solve([1, 2, 3, 4], 10))          # True (1+2+3+4)
print(ob.solve([1, 2, 3, 4], 11))          # False
print(ob.solve([0, 0, 0, 0], 0))           # True

ความซับซ้อน

• Time: O(n³) - 2 nested loops + two pointers
• Space: O(1) หรือ O(log n)

Optimization: Skip Duplicates (ถ้าต้องหาทุกชุด)

def solve_all_quadruplets(self, nums, k):
    nums.sort()
    n = len(nums)
    result = []
    
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            l, h = j + 1, n - 1
            while l < h:
                summ = nums[i] + nums[j] + nums[l] + nums[h]
                if summ == k:
                    result.append([nums[i], nums[j], nums[l], nums[h]])
                    while l < h and nums[l] == nums[l+1]:
                        l += 1
                    while l < h and nums[h] == nums[h-1]:
                        h -= 1
                    l += 1
                    h -= 1
                elif summ < k:
                    l += 1
                else:
                    h -= 1
    return result

Generalization: k-Sum

Pattern นี้ขยายได้เป็น k-Sum problem: เรียง + (k-2) nested loops + 2 pointers

LeetCode 18: 4Sum

โจทย์คลาสสิก - หา quadruplets ทั้งหมดที่ sum = target