leetcode_16

发表于   |   分类于

3Sum Closest

题目戳这

题意

给一个数组，然后零给一个目标数字target,求三个数字组合a,b,c，使得它们的和最接近target。

解法

这个跟前面的题目类似，我们先把它进行排序，然后枚举a,将另外两个指针i,j指向a后面数字序列的一头一尾，然后比较array[i]+array[j]的结果，如果比target小，说明array[i]过小，此时将i的指针往后移动，并且更新结果。反之亦然。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nlen = len(nums)
        nums.sort()
        mmax = 0x7fffffff
        result = 0
        for i in range(nlen-2):
            if i and nums[i] == nums[i-1]: # 重复的无需计算
                continue
            l = i + 1
            r = nlen-1
            while l < r:
                sm = nums[i] + nums[l] + nums[r]
                if sm < target:
                    if target - sm < mmax:
                        mmax = target-sm
                        result = sm
                    l += 1
                elif sm > target:
                    if sm - target < mmax:
                        mmax = sm - target
                        result = sm
                    r -= 1
                else:
                    return sm
            
        return result