面试题57: 和为s的数字

📖每日一句： “We hold ourselves back in ways both big and small, by lacking self-confidence, by not raising our hands, and by pulling back when we should be leaning in.” — Sheryl Sandberg

题目一：和为s的两个数字

题目描述：

输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

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

解题思想

遇题不会想暴力算法，先来看看直观的解题思路：

1. 暴力法

首先选择数组一个数字，挨个从剩下的 n-1 个数字找两数之和是不是等于 s。

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return nums[i], nums[j]
    return []

很容易看到，用到了双层循环，所以时间复杂度: $ O(n^2)$

LeetCode提交超时：26 / 36 个通过测试用例

2. 哈希表

上面的代码用了两成循环，其实转化一下思想，能不能只用一个for循环呢？

方法：TwoSum 那道题

作为一个 Pythoner，怎么会轻言放弃，办法是一定的。list 不好使，那我们还有 set 呢。也就是哈希表法：利用一次遍历，先找一个数，然后依次遍历查看 target-i 是否在这个 set 中，如果在，即返回。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        li_set = set(nums)
        for i in li_set:
            if (target - i) in li_set:
                return i, target - i
        return []

时间复杂度: $ O(n)$，只使用了一次 for 遍历数组

空间复杂度: $ O(n) $，此方法利用了一个 set

3. 双指针

就像小时候的数学刷题一样，所有的题目条件一定是最关键的，我们能够看到，还有一个很题目中关键的信息没有用到：递增数组。

做出了上面的方法后，发现其实哈希表法并没有利用题目中给出递增排序数组的特点。利用递增的特点找到空间复杂度O(1)的解题方法–双指针对撞：

算法流程可以查看此题解

取两端

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        rPointer, lPointer = 0, len(nums) - 1
        while rPointer < lPointer:

            twoSum = nums[rPointer] + nums[lPointer]
            if twoSum == target:
                return nums[rPointer], nums[lPointer]
            elif twoSum > target:
                lPointer -= 1
            else:
                rPointer += 1
        return []

4. 别忘了二分查找啊

“递增+有序”，难道二分查找不配有名字吗？

采用二分查找法缩小双指针遍历范围：
left 和 right 分别记录当前查找数组范围的最小元素下标和最大元素下标，mid=(R-L)//2+L 为中间下标；

若 nums[mid]+nums[left]>target ，则 mid 下标元素及其右边任何元素两两之和均大于 target ，只可能在 mid 左边取得，故 right=mid-1 ；

若 nums[mid]+nums[right]<target ，则 mid 下标元素及其左边任何元素两两之和均小于 target，只可能在 mid 右边取得，故 left=mid+1；

若 nums[mid]+nums[left]<=target<=nums[mid]+nums[right] 或者 left>=right 时,则结束二分查找；

若以 left>=right 结束循环，则数组中不存在和为 s 的两个元素，返回空数组。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        L,R=0,n-1
        res=[]
        mid=(R-L)//2+L
        while L<R:
            if nums[L]+nums[R]>target:
                if nums[L]+nums[mid]>target:
                    R=mid-1
                    mid=(R-L)//2+L
                elif nums[L]+nums[mid]==target:
                    res.extend([nums[L],nums[mid]])
                    break
                else:
                    R-=1
                    mid=(R-L)//2+L

            elif nums[L]+nums[R]==target:
                res.extend([nums[L],nums[R]])
                break

            else:
                if nums[R]+nums[mid]>target:
                    L+=1
                    mid=(R-L)//2+L
                elif nums[R]+nums[mid]==target:
                    res.extend([nums[mid],nums[R]])
                    break
                else:
                    L=mid+1
                    mid=(R-L)//2+L
        return res

文章参考：

• 题目来源
• Java 二分查找+双指针