leetcode刷題記第16題解法（python解析）

leetcode刷題記--> 16題解法（python解析）

• 題目定義
• 解題
• • 1. 暴力解法
  • 2. 定住一個數，然後二分查找後兩個數
  • 3. 定住一個數，然後二分查找後兩個數
  • • 實作

題目定義

給定一個包括 n 個整數的數組 nums 和 一個目标值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。傳回這三個數的和。假定每組輸入隻存在唯一答案。

例如，給定數組 nums = [-1，2，1，-4], 和 target = 1.

與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).
           

來源：力扣（LeetCode）

連結: leetcode_16題.

解題

本次使用4種方法，在leetcode上還有更多的方法，隻能說真牛逼，真聰明。

1. 暴力解法

使用暴力的方法進行搜尋（習慣性就想用暴力，這腦子）

2. 定住一個數，然後二分查找後兩個數

雙下标法，極其巧妙，可以多看看，這道題中需要注意abs絕對值，然後需要注意定一個初始值，然後使用二分法進行查找

3. 定住一個數，然後二分查找後兩個數

雙下标法，極其巧妙，可以多看看，這道題中需要注意abs絕對值，然後需要注意定一個初始值，然後使用二分法進行查找（和第二種解法不一樣的是在兩個的初始值定義的不同）

===================================================

實作

// An highlighted block
class Solution:

    def threeSumClosest(self, nums, target):
        '''
        跟第15題  差不多  先用  暴力走一把    總是懶得思考直接先暴力走一遍 然後在用其他方法跑
        '''
        if len(nums) < 3:
            return None
        list_end = []
        list_value_end = []
        for a in range(len(nums)):
            for b in range(a + 1, len(nums)):
                for c in range(b + 1, len(nums)):
                    value = abs(target - nums[a] - nums[b]-nums[c])
                    list_value_end.append(value)
                    list_end.append([nums[a] ,nums[b],nums[c]])

        min_value = min(list_value_end)

        return sum(list_end[ list_value_end.index(min_value) ])




    def threeSumClosest_1(self, nums, target):
        '''
         二分法   定義一個初始值  注意在這個方法中和下一個方法中的初始值定義方式不一樣
        '''
        nums = sorted(nums)
        res_min = 0 # 存儲最小的值
        sum_min =None
        for i in range(len(nums)):

            l =i+1
            r = len(nums)-1
            while l<r:
                three_sum = nums[i] + nums[l] + nums[r]
                res_value =  target - three_sum

                if res_min==0:
                    res_min = abs(res_value)
                    sum_min = three_sum
                if abs(res_value) <res_min:
                    res_min = abs(res_value)
                    sum_min = three_sum

                if three_sum==target:
                    return target
                elif three_sum<target:
                    l+=1
                else:
                    r-=1

        return sum_min

    def threeSumClosest_2(self, nums, target) :
        '''
        二分法   初始值定義不太好
        '''
        if len(nums)<3:
            return None
        nums.sort()
        closetNum = nums[0]+nums[1]+nums[2]
        for i in range(len(nums)):
            l = i+1
            r = len(nums)-1
            while l<r:
                threeSum = nums[i] + nums[l] + nums[r]
                if abs(threeSum-target)<abs(closetNum-target):
                    closetNum = threeSum
                if threeSum>target:
                    r-=1
                elif threeSum<target:
                    l+=1
                else:
                    return target

        return closetNum




print(Solution().threeSumClosest_2([0,2,1,-3],1))