[Leetcode][python]3Sum Closest

╰+攻爆jí腚メ 2022-06-10 06:23 135阅读 0赞

## 题目大意 ##

3sum问题的变种，寻找与目标数字最近的那一组数,返回三数之和

## 解题思路 ##

一样的遍历每个数，对剩余数组进行双指针扫描。区别仅仅在于当：  
sum = A\[left\] + A\[right\]  
(1) sum = target时直接返回  
(2) sum != target时，在相应移动left/right指针之前，先计算abs(sum-target)的值，并更新结果。

时间复杂度：O(n log n)（排序）+ O（n^2）= O（n^2）

## 代码 ##

class Solution:
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            nums.sort() # 先排序
            closest_sum = sys.maxsize
            for i in range(len(nums)-2):  # 遍历至倒数第三个，后面两个指针
                if i == 0 or nums[i] > nums[i-1]:  # 排除相同数和刚开始的时候
                    left = i + 1
                    right = len(nums) - 1
                    while left < right:
                        diff = nums[left] + nums[right] + nums[i] - target
                        if abs(diff) < abs(closest_sum):
                            closest_sum = diff
                        if diff == 0:
                            return target
                        elif diff < 0:
                            left += 1
                        else:
                            right -= 1
    
            return closest_sum + target  # 原三数之和

## 总结 ##

该题显然是考验双指针，双指针思路清晰，更容易理解。

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关 16 3Sum Closest

类似的题目有 [1 TwoSum][] [15 3Sum][] [18 4Sum][] public static int threeSumClosest

清疚/ 2022年08月10日 00:52/ 0 赞/ 50 阅读

相关 3Sum Closest ——解题报告

【题目】 Given an array S of n integers, find three integers in S such that the sum

野性酷女/ 2022年08月08日 06:13/ 0 赞/ 187 阅读

相关 Leetcode——16. 3Sum Closest

1. 概述 1.1 题目 Given an array S of n integers, find three integers in S such that th

曾经终败给现在/ 2022年06月14日 09:26/ 0 赞/ 118 阅读

相关 16. 3Sum Closest

[16. 3Sum Closest ][16. 3Sum Closest] Given an array S of n integers, find t

Love The Way You Lie/ 2022年06月08日 12:48/ 0 赞/ 150 阅读

相关 3Sum Closest

[原题链接][Link 1] 给含有n个元素的数组S，寻找出S中的三个元素，使其求和接近于所给的数字，target。并且返回这三个元素之和。你应该假设每一个输出只有一个确切

「爱情、让人受尽委屈。」/ 2022年06月06日 04:44/ 0 赞/ 174 阅读

相关 3Sum Closest

题目 Given an array S of n integers, find three integers in S such that the sum is clos

以你之姓@/ 2022年06月03日 09:11/ 0 赞/ 147 阅读

相关 16. 3Sum Closest

Given an array `nums` of n integers and an integer `target`, find three integers in `num

素颜马尾好姑娘i/ 2022年04月16日 01:39/ 0 赞/ 171 阅读

相关 [LeetCode] 3Sum Closest

Given an arrayS ofn integers, find three integers inS such that the sum is closest to a

朱雀/ 2022年03月27日 02:44/ 0 赞/ 190 阅读

相关 Leetcode 16. 3Sum Closest

[https://leetcode.com/problems/3sum-closest/][https_leetcode.com_problems_3sum-closest]

Myth丶恋晨/ 2021年12月23日 07:27/ 0 赞/ 220 阅读

相关 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to

布满荆棘的人生/ 2021年12月17日 10:39/ 0 赞/ 193 阅读