#LeetCode:16. 3Sum Closest

灆洢 2018-10-07 01:52:11

15. 3Sum 解法類似,先排序陣列,固定一個數字後,另外兩個數字就從剩下的數字前後往內縮去找總和最相近的即可。

C++(4ms)

/*******************************************************/
/* LeetCode 16. 3Sum Closest                           */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/06                                 */
/*******************************************************/
#include <cstdlib>
#include <climits>
#include <algorithm>

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        int minDistance = INT_MAX;
        int closestSum = 0;
        for(int i = 0 ; i < nums.size() - 2 ; ++i){
          for(int j = i + 1, k = nums.size() - 1 ; j < k ; ){
            int sum = nums[i] + nums[j] + nums[k];
            if(sum == target) return sum;

            int distance = abs(sum - target);
            if(distance < minDistance){
              minDistance = distance;
              closestSum = sum;
            }

            if(sum < target){
               do { ++j; } while(j < k && nums[j] == nums[j-1]);
            }
            else{ 
              do { --k; } while(j < k && nums[k] == nums[k+1]);
            }
          }
        }

        return closestSum;
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料