剑指offer--面试题57: 和为s的数字

面试题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. 别忘了二分查找啊

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