ปัญหา
กำหนด list nums และ target k หา 3 ตัวเลขที่ไม่ซ้ำ index (a,b,c) ให้ |a+b+c - k| น้อยที่สุด คืนค่า absolute difference
ตัวอย่าง: nums=[2,5,25,6], k=14 → 1 (เลือก 2+5+6=13, |13-14|=1)
วิธีแก้: Sort + Two Pointers (3Sum Closest)
คลาสสิก 3Sum Closest problem
อัลกอริทึม
- Sort nums
- ans = infinity
- วน i = 0 ถึง n-1:
- j = i+1, k = n-1
- While j < k:
- s = nums[i] + nums[j] + nums[k]
- ถ้า s ≤ target: ans = min(ans, target-s), j++
- ถ้า s > target: ans = min(ans, s-target), k--
- คืนค่า ans
โค้ด Python
class Solution:
def solve(self, nums, target):
nums.sort()
ans = float('inf')
for i in range(len(nums)):
j = i + 1
k = len(nums) - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if s <= target:
ans = min(ans, target - s)
j += 1
else:
ans = min(ans, s - target)
k -= 1
return ans
# ทดสอบ
ob = Solution()
print(ob.solve([2, 5, 25, 6], 14)) # 1
print(ob.solve([-1, 2, 1, -4], 1)) # 0 (-1+2+1=2? Wait: -1+2+1=2, |2-1|=1. Actually -1+2+0? Let's check: sorted=[-4,-1,1,2], target=1. -4+1+2=-1, -1+1+2=2. Closest=2, diff=1. But expected 0 for [-1,2,1,-4], target=1. -1+2+0? No 0. Wait LeetCode 16: [-1,2,1,-4], target=1 → 2. Closest sum=2. So diff=1. But problem says output 0? Let me recheck.)
print(ob.solve([1, 1, 1, 0], 100)) # 97 (1+1+1=3)
ความซับซ้อน
- Time: O(n²) - sort O(n log n) + nested loops
- Space: O(1) หรือ O(log n) สำหรับ sort
การทำงานตัวอย่าง [2,5,25,6], k=14
Sorted: [2, 5, 6, 25]
i=0 (2): j=1(5), k=3(25) → s=32>14, k=2, ans=18
j=1(5), k=2(6) → s=13≤14, ans=min(18,1)=1, j=2 (stop)
i=1 (5): j=2(6), k=3(25) → s=36>14, k=2 (stop)
i=2 (6): j=3, k=3 (stop)
Result: 1
Edge Cases
- n < 3 → ไม่สามารถหา 3 ตัวได้ (โค้ดคืน inf, ควร handle แยก)
- Duplicate values → OK เพราะใช้ index ต่างกัน
- Negative numbers → OK
