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

ปัญหา

กำหนด list nums และ target k ตรวจสอบว่ามี 3 ตัวเลข unique (index ต่างกัน) ที่ผลรวม = k หรือไม่

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

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

อัลกอริทึม

1. Sort nums
2. Two pointers: l=0, r=n-1
3. While l < r-1:
   • t = k - nums[l] - nums[r] (ค่าที่ต้องการหาไว้กลาง)
   • ถ้า nums[r-1] < t: l++ (เลขมากสุดยังน้อยเกินไป)
   • Else: วน m = l+1 ถึง r-1:
     • ถ้า nums[m] > t: r--, break
     • ถ้า nums[m] == t: return True
4. Return False

โค้ด Python

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, len(nums) - 1
        
        while l < r - 1:
            t = k - nums[l] - nums[r]
            if nums[r - 1] < t:
                l += 1
                continue
            for m in range(l + 1, r):
                if nums[m] > t:
                    r -= 1
                    break
                if nums[m] == t:
                    return True
        return False

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

ความซับซ้อน

• Time: O(n²) - worst case
• Space: O(1) หรือ O(log n)

Standard 3Sum Approach (อีกวิธี)

def solve_standard(self, nums, k):
    nums.sort()
    n = len(nums)
    for i in range(n - 2):
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == k:
                return True
            elif s < k:
                l += 1
            else:
                r -= 1
    return False

Standard approach เข้าใจง่ายกว่าและพบได้เร็วขึ้นในหลายกรณี

LeetCode 15: 3Sum (Find all triplets) / 3Sum Existence

เวอร์ชันนี้แค่เช็คมี/ไม่มี (Boolean) ไม่ต้องหาทุก triplet