LeetCode如何找出和為s的兩個(gè)數(shù)字

題目描述

輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字 s，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是 s。如果有多對(duì)數(shù)字的和等于 s，則輸出任意一對(duì)即可。

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

題目樣例

示例

• 輸入：nums = [2,7,11,15], target = 9

• 輸出：[2,7] 或者 [7,2]

• 輸入：nums = [10,26,30,31,47,60], target = 40

• 輸出：[10,30] 或者 [30,10]

題目思考

1. 如何利用遞增排序的條件?
2. 如何做到空間復(fù)雜度是 O(1)?

解決方案

思路

• 一個(gè)比較容易想到的思路是使用一個(gè)集合, 然后遍歷一遍數(shù)組: 如果                         target-當(dāng)前的數(shù)已經(jīng)在集合的話, 就說(shuō)明找到了一對(duì)結(jié)果, 直接返回即可; 否則就把當(dāng)前的數(shù)加入集合
• 但這個(gè)思路沒(méi)有利用到遞增排序的條件, 且使用了額外的空間, 并不是最優(yōu)解
• 如何利用排序的條件呢? 通常有兩種思路:                         二分或者雙指針
• 這里如果使用二分的話, 意味著固定當(dāng)前的數(shù)為起點(diǎn), 然后二分查找右側(cè)區(qū)間                         target-當(dāng)前的數(shù)是否存在, 會(huì)額外引入 logN 的時(shí)間復(fù)雜度, 還沒(méi)有上面的思路好
• 所以嘗試使用雙指針的做法, 將兩個(gè)下標(biāo) i 和 j 初始化為數(shù)組的頭和尾, 然后往中間靠攏
• 根據(jù)當(dāng)前的和, 具體分為以下三種情況:
1. nums[i] + nums[j] == target: 找到一對(duì)滿足條件的數(shù)字了, 直接返回
2. nums[i] + nums[j] < target: 當(dāng)前和小于 target, 因?yàn)閿?shù)組有序, 如果保留 nums[i], 而 j 繼續(xù)往左的話, 新的和肯定更小于 target, 所以 nums[i]可以被安全排除, 即 i 直接加 1
3. nums[i] + nums[j] > target: 當(dāng)前和大于 target, 因?yàn)閿?shù)組有序, 如果保留 nums[j], 而 i 繼續(xù)往右的話, 新的和肯定更大于 target, 所以 nums[j]可以被安全排除, 即 j 直接減 1
• 這樣遍歷下去最終肯定 i 和 j 會(huì)相遇, 此時(shí)退出循環(huán), 說(shuō)明沒(méi)找到滿足條件的數(shù)字對(duì), 返回空數(shù)組即可
• 使用雙指針做法后, 時(shí)間復(fù)雜度沒(méi)有變差, 也不需要額外的空間了

復(fù)雜度

• 時(shí)間復(fù)雜度 O(N): 只遍歷了一遍數(shù)組
• 空間復(fù)雜度 O(1): 只使用了幾個(gè)變量

代碼

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 雙指針
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                # 找到一對(duì)滿足條件的數(shù)字, 直接返回
                return [nums[i], nums[j]]
            elif nums[i] + nums[j] < target:
                # 當(dāng)前和小于target, 只能是i向右移, 這樣后續(xù)和才會(huì)更大
                i += 1
            else:
                # 當(dāng)前和大于target, 只能是j向左移, 這樣后續(xù)和才會(huì)更小
                j -= 1
        return []