iT邦幫忙

2024 iThome 鐵人賽

DAY 2
0

https://ithelp.ithome.com.tw/upload/images/20240919/20169309DQdB5u6qkl.png題目要我在它給的整數組 nums 裡找三個數,讓它們的和最接近目標值 target,且保證每個輸入都有唯一解,這種題目通常要考慮很多不同的組合來找到最完美的結果,所以怎樣優化搜索就是關鍵。

了解題目要求
給一個整數組和一個目標數 target,找到三個整數,讓它們的和最接近目標數,輸出:是三個整數的和,不是三個整數本身,題目保要證輸入只有唯一解,所以可以不考慮重複解,直覺用暴力解是一個方法,選三個數的所有組合,算其和,再比較所有可能結果差異,就可以找到最接近的,但這種暴力解的時間複雜度是
𝑂(n的三次方),如果數組長度長達500效率就不高,所以可以考慮更好的雙指針方式來減少時間複雜度,用排序和雙指針法
這題可先排序數組,再用雙指針的方式來縮小搜尋範圍。

步驟 :
先把數組 nums 排序,這樣可以輕鬆用雙指針來搜尋,再固定一個數,用雙指針法,遍歷數組,對每個元素 nums[i],設它是三個數理的第一個數,然後用兩個指針在剩下的數組範圍內找另外兩個數,左指針 left 指向 i+1 位置,右指針 right 指向數組尾,然後算三數的和 sum = nums[i] + nums[left] + nums[right],用sum 與跟target 做比較,如果 sum 小於 target,左指針 left 右移,因為它需要更大的數來逼近 target,如果 sum 大於 target,右指針 right 左移,因為它需要更小的數來逼近 target,如果sum 剛好等於 target,直接返回結果,這是最理想的情況,然後記錄最接近的結果,每次算 sum ,都要跟進最接近 target 的結果,在更接近時更新結果。
技巧:
排序數組可以讓雙指針法更有效,通過調整左右指針來縮小搜索範圍,取代暴力搜索(雙指針搜索),一找到 sum == target 的情況,就可以提前返回結果,不用繼續算。

程式碼:
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
#排數組
nums.sort()
closest_sum = float('inf') # 初始化一個很大的數當成最接近的和

    #用雙指針法遍歷數組
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1  # 初始化左右指針
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]  # 算當前三數的和
            
            #如果當前總和剛好等於目標,直接返回
            if current_sum == target:
                return current_sum
            
            #更新最接近的和
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            
            #調整指針位置
            if current_sum < target:
                left += 1  # 移動左指針,試著增加和
            else:
                right -= 1  # 移動右指針,試著減少和
    
    return closest_sum

困難心得:
我對對雙指針法不是很熟悉,是問chat gpt才知道這題需要用這個解法,我一開始一直不知道怎麼調整指針來優化搜尋範圍,處理一樣的最接近和,當有多個三數和都接近 target ,只能返回最小差異的和,還有邊界條件,如果數組長度很接近最小要求(像是剛好只有三個元素),還是要正確處理。


上一篇
D1:Q2 Add Two Numbers
下一篇
D5:Q22Generate Parentheses
系列文
Leecode刷題28
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言