โจทย์ 3Sum Closest ใน C++ (หา 3 ตัวที่รวมกันใกล้ Target มากที่สุด)

โจทย์ปัญหา

ได้รับอาร์เรย์ nums ขนาด n และค่า target ให้หา 3 จำนวนในอาร์เรย์ ที่ผลรวม ใกล้เคียงกับ target มากที่สุด คืนค่าผลรวมนั้น (รับประกันว่ามีคำตอบเพียง 1 ชุด)

ตัวอย่าง

นำเข้า: nums = [-1, 2, 1, -4], target = 1
ผลลัพธ์: 2
คำอธิบาย: Triplet [-1, 2, 1] ให้ผลรวม 2 ใกล้ target=1 มากที่สุด (ความต่าง = 1)

แนวคิดการแก้ปัญหา (Two Pointers + Sorting)

1. Sort อาร์เรย์
2. กำหนด ans = 0, diff = INT_MAX
3. วนลูป i จาก 0 ถึง n-1:
   • ตั้ง left = i+1, right = n-1
   • ขณะ left < right:
     • sum = nums[i] + nums[left] + nums[right]
     • ถ้า |target - sum| < diff: อัปเดต ans = sum, diff = |target - sum|
     • ถ้า sum == target: คืนค่า sum ทันที (เจอคำตอบที่ดีที่สุดแล้ว)
     • ถ้า target: right-- (ลดผลรวม)
     • ถ้า sum < target: left++ (เพิ่มผลรวม)
4. คืนค่า ans

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int diff = INT_MAX;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right] + nums[i];
                if (abs(target - sum) < diff) {
                    ans = sum;
                    diff = abs(target - sum);
                }
                if (sum == target) return sum;
                else if (sum > target) right--;
                else left++;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-1, 2, 1, -4};
    cout << ob.threeSumClosest(v, 1);
    return 0;
}

ผลลัพธ์

2

คำอธิบายเพิ่มเติม

• ความซับซ้อนด้านเวลา: O(n²) (Sort O(n log n) + Two pointers O(n²))
• ความซับซ้อนด้านพื้นที่: O(1) หรือ O(log n) สำหรับ sorting stack
• เทคนิค Two Pointers ใช้ได้เพราะอาร์เรย์ถูก Sort แล้ว
• ข้ามค่าซ้ำได้ด้วยการ while (left < right && nums[left] == nums[left+1]) left++ เพื่อประสิทธิภาพ