剑指 Offer 57. 和为s的两个数字

题目描述

https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
输入一个递增排序的数组和一个数字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

解题思路

双指针
设定一头一尾两个指针i，j。
如果两个指针指向的数的和等于target，返回结果；
如果两个指针指向的数的和小于target，减少j；
如果两个指针指向的数的和大于target，增大i；
正确性证明：没遇到的状态都更加极端，不可能碰见，因此尽管消除就好。
哈希表
找某一个数存在不存在，可以用哈希
1. 使用set
将list用set(nums)函数转换为nums_set。
对每一个nums[i]，如果target - nums[i]在set里面，则nums[i]和target - nums[i]就是我们想要的结果。if target - nums[i] in nums_set是O(1)的复杂度哦。
Q：如果数组里有两个30，我要找组成60的两个数，可是set里面只有一个30，怎么办？
A：没事，30 + 30 = 60，我们要找的仅仅是第二个30，不是找两个。set里面有一个30了。
2. 使用dict
dict的好处是可以存dict[want] = nums[i]，如果之后遍历的时候有一个别的nums[i]值恰好in dict，就证明找到了。这种方法的好处是不用遍历整个数组把每个value置1再找key。
二分法
由于数组是有序的，因此target - nums[i]可以使用二分法在nums数组中找到。这样复杂度比O(n^2)比起来优化到了O(nlogn)。
注意二分法的while判断是带等号的。

解题代码

双指针：

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            sum_result = nums[i] + nums[j]
            if sum_result == target:
                return [nums[i], nums[j]]
            elif sum_result > target:
                j -= 1
            elif sum_result< target:
                i += 1

哈希表：
使用set：

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        nums_set = set(nums)
        for i in range(len(nums)):
            if target - nums[i] in nums_set:
                return [nums[i], target - nums[i]]

使用dict：

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hash_map = {}
        for i in range(len(nums)):
            want = target - nums[i]
            if nums[i] in hash_map:
                return [nums[i], hash_map[nums[i]]]  ## 现在的nums[i]就是以前的want
            else:
                hash_map[want] = nums[i]

二分法：

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for k in range(len(nums)):
            want = target - nums[k]
            i, j = 0, len(nums) - 1
            while i <= j:  # 二分法这里要用等号,不然分析不到i==j的情况
                mid = int((i + j) / 2)
                if nums[mid] == want:
                    return [nums[k], want]
                elif nums[mid] > want:
                    j = mid - 1
                elif nums[mid] < want:
                    i = mid + 1

执行结果

双指针：120ms 25.5MB
哈希表：136ms 31.2MB和和188ms 27.6MB
二分法：1412ms 25.2MB