剑指 Offer 之面试题 57: 和为 s 的数字

2022 年 4 月 04 日
本文字数：1974 字
阅读完需：约 6 分钟

和为 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^51 <= nums[i] <= 10^6

复制代码

解题思想

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

暴力法

首先选择数组一个数字，挨个从剩下的 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 个通过测试用例

哈希表

上面的代码用了两成循环，其实转化一下思想，能不能只用一个 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

双指针

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

做出了上面的方法后，发现其实哈希表法并没有利用题目中给出递增排序数组的特点。利用递增的特点找到空间复杂度 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 []

复制代码

别忘了二分查找啊

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

采用二分查找法缩小双指针遍历范围：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