寫在前面:
程序員分兩種翻斟，會(huì)算法的程序員和不會(huì)算法的程序員匿垄。幾乎沒(méi)有一個(gè)一線互聯(lián)網(wǎng)公司招聘任何類別的技術(shù)人員是不考算法的嚣州，程序猿們都懂的，現(xiàn)在最權(quán)威流行的刷題平臺(tái)就是 LeetCode硝拧。
Question:
3Sum Closest
Difficulty:Medium Tag:Array
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution:
以下代碼皆是本人用 C++寫的，覺(jué)得還不錯(cuò)的話別忘了點(diǎn)個(gè)贊哦葛假。各位同學(xué)們?nèi)绻衅渌咝Ы忸}思路還請(qǐng)不吝賜教障陶，多多學(xué)習(xí)。
A1聊训、暴力解法
粗暴進(jìn)行循環(huán)遍歷抱究，問(wèn)題復(fù)雜化，不可取
此處不再給示例
A2带斑、雙指針解法
減少了部分一定不成立情況的計(jì)算鼓寺，同
LeetCode刷算法題 - 11. Container With Most Water(盛最多水的容器)
算法時(shí)間復(fù)雜度 O(n^2)，Runtime: 7 ms勋磕，代碼如下
int x=[](){
std::ios::sync_with_stdio(false); //關(guān)閉STDIN和CIN同步 減少CIN讀入的時(shí)間妈候，可以減少50%以上。
cin.tie(NULL);
return 0;
}();
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end());
int left = 0, right = (int)nums.size()-1, res = INT_MIN, gap = INT_MAX;
for (int i=0; i<nums.size(); i++) {
if (i>0 && nums[i]==nums[i-1]) continue;
left = i+1;
right = (int)nums.size()-1;
while (left<right) {
int sum = nums[i]+nums[left]+nums[right];
if (sum == target) {
return sum;
} else if (sum < target) {
left++;
} else if (sum > target){
right--;
}
if (abs(sum-target) < gap) {
gap = abs(sum-target);
res = sum;
}
}
}
return res;
}
};
