最接近的三數之和 - LintCode

描述

給一個包含 n 個整數的數組 S, 找到和與給定整數 target 最接近的三元組，傳回這三個數的和。

隻需要傳回三元組之和，無需傳回三元組本身
           

樣例

例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元組是 -1 + 2 + 1 = 2.

挑戰

O(n^2) 時間, O(1) 額外空間。

思路

由于不需要傳回三元組本身，可以對數組排序。對于位置i，j = i + 1，k = len - 1，根據sum = nums[i] + nums[j] + nums[k]與target的大小來調整j，k的值。

#ifndef C59_H
#define C59_H
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int threeSumClosest(vector<int> nums, int target) {
        // write your code here
        if (nums.empty()|| nums.size()<)
            return ;
        int len = nums.size();
        int res = nums[]+nums[]+nums[len-];
        //隻尋找三元組不必考慮順序
        sort(nums.begin(), nums.end());
        //當sum大于target,k向前移動,sum值變小
        //當sum小于target,j向後移動,sum值變大
        for (int i = ; i < len - ; ++i)
        {
            int j = i + ;
            int k = len - ;
            while (j < k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                res = absVal(res - target)<absVal(sum - target) ? res : sum;
                if (sum>target)
                    --k;
                else if (sum == target)
                    return target;
                else
                    ++j;
            }
        }
        return res;
    }
    int absVal(int a)
    {
        if (a >= )
            return a;
        else
            return -a;
    }
};
#endif