no.
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Array、Two Pointers、Sorting
一、題目
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closet to target.
Return *the sum of the three integers`.
You may assume that each input would have exactly one solution.
Example 1:
- Input: nums = [-1,2,1,-4], target = 1
- Output: 2
- Explanation: The sum that is closet to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
- Input: nums = [0,0,0], target = 1
- Output: 0
- Explanation: The sum that is closet to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-10^4 <= target <= 10^4
二、分析
- 若用暴力解求解的話，時間複雜度為 \(O(n^3)\)。
- 故我們可以嘗試先進行排序來簡化問題，時間複雜度為\(O(n\log n)\)。
- 此題因為是找最接近的，所以無法用 HashMap 解。
- 使用 Two Pointer，並藉由比較和與
target的差值來找到最接近的解。
三、解題
1. Two Pointer
- Time complexity: \(O(n^2)\)
- Space complexity: \(O(1)\)
int threeSumCloset(vector<int>& nums, int target) {
int res = INT_MAX;
int n = nums.size();
if (n == 3) return accumulate(nums.begin(), nums.end(), 0); // 當 n = 3 時，這三個值必為解。
sort(nums.begin(), nums.end()) // 排序
for (int i = 0; i < n-2; i++) {
int left = i+1, right = n-1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (abs(res - target) > abs(sum - target))
res = sum;
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
return sum; // 差值等於 0 時，不會再有更小的差值
}
}
}
return res;
}