欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构算法操作试题(C++/Python)——最接近的三数之和

程序员文章站 2022-04-25 14:41:56
...

文章目录


数据结构算法操作试题(C++/Python):数据结构算法操作试题(C++/Python)——目录


1. 题目

leetcode 链接:https://leetcode-cn.com/problems/3sum-closest/comments/

数据结构算法操作试题(C++/Python)——最接近的三数之和

2. 解答

python : 108ms, 13MB, 92%

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        if sum(nums[-3:]) <= target:
            return sum(nums[-3:])
        if sum(nums[:3]) >= target:
            return sum(nums[:3])
        pre_flag = "flag"
        flag = pre_sum_val = sum_val = first_flag = 0
        for i in range(len(nums) - 2):
            start = i + 1
            end = len(nums) - 1
            while start < end:
                sum_val = nums[start] + nums[end] + nums[i]
                if sum_val > target:
                    end -= 1
                    flag = 0
                elif sum_val < target:
                    start += 1
                    flag = 1
                else:
                    return target
                if pre_flag != flag and pre_flag != "flag":
                    if not first_flag:
                        minDis = self.judgeAbs(sum_val, pre_sum_val, target)
                        first_flag = 1
                    minDis = self.judgeAbs(self.judgeAbs(sum_val, pre_sum_val, target), minDis, target)
                    pre_flag = "flag"
                else:
                    pre_flag = flag
                    pre_sum_val = sum_val
        return minDis
    
    def judgeAbs(self, sum_1, sum_2, target):
        return sum_2 if abs(sum_1 - target) >= abs(sum_2 - target) else sum_1

其他方法看 leetcode 链接 评论区~