題目描述

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

• 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)?

解決方案

思路

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

復(fù)雜度

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

代碼

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:
                # 找到一對滿足條件的數(shù)字, 直接返回
                return [nums[i], nums[j]]
            elif nums[i] + nums[j] < target:
                # 當前和小于target, 只能是i向右移, 這樣后續(xù)和才會更大
                i += 1
            else:
                # 當前和大于target, 只能是j向左移, 這樣后續(xù)和才會更小
                j -= 1
        return []