LeetCode-Algorithms-16.最接近的三數之和（C）

1. 題目描述

給定一個包括 n 個整數的數組 nums 和 一個目标值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。傳回這三個數的和。假定每組輸入隻存在唯一答案。

例如，給定數組 nums = [-1，2，1，-4], 和 target = 1.

與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).
           

2. 送出記錄

3. 算法思想

為了能夠找出與 target 最接近的整數和，需要先對數組 nums 進行排序。

看到題目，我最先想到的是暴力解決，三層 for 循環,但是這種方法顯然不是最好的，因為時間複雜度比較高 O(n3).之前在評論區看過雙指針法，做了“三數之和”這道題，我真的是要實名誇贊這種解法，是以這次也毫不猶豫選擇了雙指針法。算法思想如下：

先給整數和sum賦一個初始值 sum = nums[0]+nums[1]+nums[2]；

在for循環中設定左指針 left = i+1 ； 右指針 right 指向數組最後一位 right = numsSize-1;

需要注意的是為了能夠找出與 target 最接近的整數和，需要對每個整數和進行比較，選出最接近 target 的結果。

4. 代碼實作

int threeSumClosest(int* nums, int numsSize, int target){
    //從小到大排序
    int temp = 0;
    for(int i=0;i <= numsSize-2;i++){
        for(int j=i+1;j <= numsSize-1;j++){
            if(nums[i] > nums[j]){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }
    //雙指針
    int left,right,sum = nums[0]+nums[1]+nums[2];
    for(int i = 0;i< numsSize-2;i++){        
        left = i+1;
        right = numsSize-1;                
        while(left < right){
            temp = nums[i]+nums[left]+nums[right];
            if(temp > target){
                right--; 
            }else if(temp < target){
                left++;
            }else{
                return temp;
            }
            if(fabs(temp-target) < fabs(sum-target)){
                sum = temp;
            }      
        }        
    }
    return sum;
}