Bài toán 3Sum Closest trong C++

Cho mảng nums có n số nguyên và một giá trị target. Tìm ba số nguyên trong nums sao cho tổng của chúng gần target nhất. Trả về tổng của ba số đó. Giả định mỗi đầu vào có đúng một nghiệm. Ví dụ: mảng [-1,2,1,-4], target = 1 → bộ ba [-1,2,1] có tổng gần nhất = 2.

Giải pháp:

• Sắp xếp mảng, ans := 0, diff := ∞, n := size.
• Với i từ 0 đến n-1:
  • left := i+1, right := n-1.
  • While left < right:
    • temp := nums[left] + nums[right] + nums[i].
    • Nếu |target - temp| < diff → ans := temp, diff := |target - temp|.
    • Nếu temp = target → trả về temp; nếu temp > target → right--; ngược lại left++.
• Trả về ans.

Ví dụ 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 temp = nums[left] + nums[right] + nums[i];
                if (abs(target - temp) < diff) {
                    ans = temp;
                    diff = abs(target - temp);
                }
                if (temp == target) return temp;
                else if (temp > target) right--;
                else left++;
            }
        }
        return ans;
    }
};

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

Đầu vào

[-1,2,1,-4] 1

Đầu ra

2