題目

167. 兩數(shù)之和 II - 輸入有序數(shù)組

難度簡(jiǎn)單629 收藏 分享 切換為英文 接收動(dòng)態(tài) 反饋

給定一個(gè)已按照**非遞減順序排列 **的整數(shù)數(shù)組 numbers ，請(qǐng)你從數(shù)組中找出兩個(gè)數(shù)滿足相加之和等于目標(biāo)數(shù) target 。

函數(shù)應(yīng)該以長(zhǎng)度為 2 的整數(shù)數(shù)組的形式返回這兩個(gè)數(shù)的下標(biāo)值。numbers 的下標(biāo) 從 1 開始計(jì)數(shù) ，所以答案數(shù)組應(yīng)當(dāng)滿足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假設(shè)每個(gè)輸入 只對(duì)應(yīng)唯一的答案 ，而且你 不可以 重復(fù)使用相同的元素。

1. 踉踉蹌蹌?wù){(diào)出來的二分解法

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        for k,v in enumerate(numbers):
            new = numbers[0:k] + numbers[k+1:]  # 剔除元素本身，構(gòu)造除本元素外的list
            l, r = 0, len(new) - 1
            while l < r:                
                mid = (l + r + 1) // 2
                if new[mid] <= target - v:
                    l = mid
                else:
                    r = mid - 1
            if new[l] + v == target: # 考慮到從numbers中剔除的數(shù)據(jù)可能是目標(biāo)之前也可能在目標(biāo)之后
                if l >= k:
                    return k+1, l + 2
                else:
                    return k+1, l + 1

看了官方題解后，發(fā)現(xiàn)自己想多了？？？下面的代碼也能AC。。。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        for k,v in enumerate(numbers):            
            l, r = 0, len(numbers) - 1
            while l < r:                
                mid = (l + r + 1) // 2
                if numbers[mid] <= target - v:
                    l = mid
                else:
                    r = mid - 1
            if numbers[l] + v == target: 
                return k+1, l + 1
        return [-1, -1]

2. 官方優(yōu)美的二分解法 題解鏈接

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            low, high = i + 1, n - 1
            while low <= high:
                mid = (low + high) // 2
                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]
                elif numbers[mid] > target - numbers[i]:
                    high = mid - 1
                else:
                    low = mid + 1
        
        return [-1, -1]

3. 哈？雙指針？什么黑科技

看了題解的文字描述寫出的雙指針

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        l, r = 0, len(numbers) - 1
        while numbers[l] + numbers[r] != target:
            if numbers[l] + numbers[r] > target:
                r = r - 1
            elif numbers[l] + numbers[r] < target:
                l = l + 1
        return [l + 1, r + 1]

官方題解的雙指針：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low, high = 0, len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            elif total < target:
                low += 1
            else:
                high -= 1

        return [-1, -1]

初始時(shí)兩個(gè)指針分別指向第一個(gè)元素位置和最后一個(gè)元素的位置。每次計(jì)算兩個(gè)指針指向的兩個(gè)元素之和，并和目標(biāo)值比較。如果兩個(gè)元素之和等于目標(biāo)值，則發(fā)現(xiàn)了唯一解。如果兩個(gè)元素之和小于目標(biāo)值，則將左側(cè)指針右移一位。如果兩個(gè)元素之和大于目標(biāo)值，則將右側(cè)指針左移一位。移動(dòng)指針之后，重復(fù)上述操作，直到找到答案。

使用雙指針的實(shí)質(zhì)是縮小查找范圍。那么會(huì)不會(huì)把可能的解過濾掉？答案是不會(huì)。假設(shè) 是唯一解，其中 。初始時(shí)兩個(gè)指針分別指向下標(biāo) 和下標(biāo) ，左指針指向的下標(biāo)小于或等于 ，右指針指向的下標(biāo)大于或等于 。除非初始時(shí)左指針和右指針已經(jīng)位于下標(biāo) 和 ，否則一定是左指針先到達(dá)下標(biāo) 的位置或者右指針先到達(dá)下標(biāo) 的位置。

如果左指針先到達(dá)下標(biāo) 的位置，此時(shí)右指針還在下標(biāo) 的右側(cè)， ，因此一定是右指針左移，左指針不可能移到 的右側(cè)。

如果右指針先到達(dá)下標(biāo) 的位置，此時(shí)左指針還在下標(biāo) 的左側(cè)，，因此一定是左指針右移，右指針不可能移到 的左側(cè)。

由此可見，在整個(gè)移動(dòng)過程中，左指針不可能移到 的右側(cè)，右指針不可能移到 的左側(cè)，因此不會(huì)把可能的解過濾掉。由于題目確保有唯一的答案，因此使用雙指針一定可以找到答案。

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。