python - 找出总和最接近给定数字的三个数字

Question

我正在尝试解决一个问题，

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

我的解决方案是:从数组中取出一个数字 (number_1)，将目标设置为 target - 该数字并找到另外两个最接近新目标的数字。这样:number_1 + number_2 + number_3 将最接近，因为 number_2 + number_3 将最接近目标 - number_1。

我在 https://leetcode.com/problems/3sum-closest/description/ 尝试了我的解决方案.

我的解决方案是:

def threeSumClosest(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    closest_sum = nums[0] + nums[1] + nums[2]

    for i in range(len(nums)):

        # Create temp array excluding a number

        if i!=len(nums)-1:
            temp = nums[:i] + nums[i+1:]

        else:
            temp = nums[:len(nums)-1]


        # Sort the temp array and set new target to target - the excluded number

        temp = sorted(temp)            
        l, r = 0, len(temp) -1 
        t = target - nums[i]

        while(l<r):

            if temp[l] + temp[r] == t:
                return target

            elif temp[l] + temp[r] > t:

                if abs(temp[l] + temp[r] + nums[i] - target) < abs(closest_sum - target):
                    closest_sum = temp[l] + temp[r] + nums[i]

                r = r - 1

            else:

                if abs(temp[l] + temp[r] + nums[i] - target) < abs(closest_sum - target):
                    closest_sum = temp[l] + temp[r] + nums[i]

                l = l + 1


        return closest_sum

它通过了 125 个测试用例中的 80 个，因此解决方案逻辑对我来说看起来足够好。

它失败了:

Input:
[0,2,1,-3]
1
Output:
3
Expected:
0

无法理解为什么会失败以及如何让我的逻辑保持一致。

感谢您的帮助。

Answer 1

你有几个错误，第一个是愚蠢的，你在 return closest 中有一个额外的缩进，第二个没有检查更新 closest 在第三个 if 语句. 此代码已被接受:

class Solution(object):
def threeSumClosest(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    closest = nums[0] + nums[1] + nums[2]

    #if len(nums)==3:
    #    return closest

    for i in range(len(nums)):
        if i!=len(nums)-1:
            temp = nums[:i] + nums[i+1:]
        else:
            temp = nums[:len(nums)-1]

        temp = sorted(temp)

        l, r = 0, len(temp) -1 
        t = target - nums[i]

        while(l < r):
            if abs(temp[l] + temp[r] + nums[i] - target) < abs(closest - target):
                    closest = temp[l] + temp[r] + nums[i]

            if temp[l] + temp[r] == t:

                return target
            elif temp[l] + temp[r] > t:
                r = r - 1
            else:
                l = l + 1

    return closest

这是一个公认的 C++ 解决方案，运行时间为 O(n^2):

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.size() - 2; i++) {
            int l = i + 1, r = nums.size() - 1;

            while (l < r) {
                if(abs(nums[i] + nums[l] + nums[r] - target) < abs(target - ans)) {
                    ans = nums[i] + nums[l] + nums[r];
                }
                if(nums[r] + nums[l] > target - nums[i]) r = r - 1;
                else l = l + 1;
            }
        }
        return ans;
    }
};