標(biāo)簽：array, medium

問題描述

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.

給定包含n個(gè)整數(shù)的數(shù)組nums和整數(shù)target，在數(shù)組中尋找3個(gè)整數(shù)，使得3個(gè)整數(shù)的和與target的值最接近。返回3個(gè)整數(shù)的和。假設(shè)每個(gè)輸入只有一個(gè)解。

例子：
給定數(shù)組nums = [-1, 2, 1, -4]和target = 1。
最接近target值的和是2 (-1 + 2 + 1 = 2)。

解決方案

方法一：暴力方法

遍歷數(shù)組中的任意3個(gè)元素，計(jì)算其和以及與target的差，選取差最小的和。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        int minDiff = INT_MAX;
        int closestSum = 0;
        for(int i = 0; i < len - 2; i++) {
            for(int j = i + 1; j < len - 1; j++) {
                for(int k = j + 1; k < len; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    int diff = target > sum ? target - sum : sum - target;
                    if(diff < minDiff) {
                        minDiff = diff;
                        closestSum = sum;
                    }
                }
            }
        }
        return closestSum;
    }
};

算法分析

• 運(yùn)行時(shí)間：256 m
• 時(shí)間復(fù)雜度：Θ(n³)。

方法二：排序法

首先對(duì)數(shù)組進(jìn)行排序。接著，選定一個(gè)元素i作為第一個(gè)元素。然后，從數(shù)組兩端向中間遍歷，選取剩下的兩個(gè)元素j和k。
如果A[i] + A[k] + A[j]的值小于target，則增加j的索引，否則減少k的索引。因?yàn)閿?shù)組是有序的，這里有三種情況：

• A[j] + A[k] == target - A[i]，此時(shí)三個(gè)元素的和等于target，差值最小；
• A[j] + A[k] < target - A[i]，因此需要增加j的索引，使值增加。
• A[j] + A[k] > target - A[i]，此時(shí)只有減少k的索引，才能減少兩個(gè)元素的和值。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        int minDiff = INT_MAX;
        int closestSum = 0;
        sort(nums.begin(), nums.end());

        for(int i = 0; i < len - 2; i++) {
            int j = i + 1;
            int k = nums.size() - 1;
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int diff = sum - target > 0 ? sum - target : target - sum;
                if (diff < minDiff) {
                    minDiff = diff;
                    closestSum = sum;
                }
                int sum2 = nums[j] + nums[k];
                if (sum2 > target - nums[i]) {
                    k--;
                } else if (sum2 < target - nums[i]) {
                    j++;
                } else {
                    break;
                }
            }
        }
        return closestSum;
    }
};

算法分析

• 程序運(yùn)行時(shí)間：12ms
• 排序算法的復(fù)雜度為O(nlog(n))，for循環(huán)的復(fù)雜度為O(n²)。因此，算法的整體時(shí)間復(fù)雜度為O(n²)。