LeetCode刷算法 - 16. 最接近三数之和

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接(英文)

LeetCode原题链接(中文)

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

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++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、暴力解法

粗暴进行循环遍历，问题复杂化，不可取
此处不再给示例

A2、双指针解法

减少了部分一定不成立情况的计算，同
LeetCode刷算法题 - 11. Container With Most Water(盛最多水的容器)

算法时间复杂度 O(n^2)，Runtime: 7 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少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;
    }    
};

引用相关

LeetCode 官网