leetcode-18 | 四数之和 中等难度

16. 最接近的三数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：
答案中不可以包含重复的四元组。

例如
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

思考

类似16，我们考虑到不重复，所以还是使用首尾指针方式

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

        resu = nums[0]+nums[1]+nums[2]
        i = 0
        nums.sort()
        while i < len(nums):
            j = i+1
            k = len(nums) - 1
            while j < k:
                sum = nums[i] + nums[j] + nums[k]
                if (abs(sum - target) < abs(resu - target)):
                    resu = sum
                if sum < target:
                    j += 1
                elif sum > target:
                    k -= 1
                else:
                    #sum == target
                    return target
            i+=1
        return resu

结果：

执行用时 : 160 ms, 在3Sum Closest的Python提交中击败了30.13% 的用户
内存消耗 : 11.5 MB, 在3Sum Closest的Python提交中击败了41.60% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	160 ms	11.5MB	python