• 分类：Array

• 考察知识点：Array(数组遍历) 动态规划

• 最优解时间复杂度：O(n^2)

16. 3Sum Closest

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.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

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

代码：

我的解法:

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        #排序，预处理一下
        nums.sort()
        res=0
        
        if len(nums)<=3:
            for n in nums:
                res+=n
        else:
            #初始化
            res=nums[0]+nums[1]+nums[len(nums)-1]
            distance=abs(res-target)

            for i in range(len(nums)-2):
                if i>0:
                    if nums[i]==nums[i-1]:
                        continue
                j=i+1
                k=len(nums)-1
                while(k>j):
                    # 去掉重复的
                    if j>=i+2 and k<=len(nums)-2:
                        if nums[j]==nums[j-1]:
                            j+=1
                        elif nums[k]==nums[k+1]:
                            k-=1

                    if abs((nums[i]+nums[j]+nums[k])-target)<distance:
                        res=nums[i]+nums[j]+nums[k]
                        distance=abs(res-target)


                    if (nums[i]+nums[j]+nums[k])>target:            
                                k-=1
                    elif (nums[i]+nums[j]+nums[k])<target:
                                j+=1
                    else:
                        return target

        return res

讨论：

1.没啥可说的，完全是3Sum的升级版，总体还是和3Sum的思路一模一样

3Sum Closest