16. 3Sum Closest
1.問題

2.想法
提問
function header, parameter
test input
說明想法
對序列後排序
使用兩個迴圈
分別使用3個指標, 依題意的目的是要計算總和與目標值的差值
若差值 == 0, 則記錄i, j , k的數值
若差值 < 0, 則表示總和太小, 讓j++
若差值 > 0, 則表示總和太大, 讓k--
測試計算複雜度: O(n^2) ?
3.程式碼
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
vector<vector<int>> res;
int size = nums.size();
if (size < 3) {
return 0;
}
int value = INT_MAX, minSum = -1;
sort(nums.begin(), nums.end());
for (int i = 0; i < size; i++) {
int j = i + 1;
int k = size - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
int diff = sum - target;
if (diff == 0){
return sum;
} else if (diff > 0) {
k--;
} else {
j++;
}
if (abs(diff) < value) {
value = abs(diff);
minSum = sum;
}
}
}
return minSum;
}
};
Last updated