LeetCode日常-简单-面试题57. 和为s的两个数字

本文最后更新于：2020年9月27日 晚上

题目

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

示例 1：

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

示例 2：

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

限制：

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

自解

思路

从后往前，先确定比较大的那个数，这样能较快的减少无用状态
由于只有两个数，确定了比较大的数以后，与目标相减一下就能得到结果，判断一下这个结果是否在记录中即可。

代码

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1, 0, -1):
            if nums[i] > target:
                continue
            if target-nums[i] in nums:
                return nums[i], target-nums[i]

效率

执行用时：192 ms
内存消耗：24.9 MB

大佬解法

思路

利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)
注意本题的 nums 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1)

算法流程：

初始化： 双指针 i, j分别指向数组 nums 的左右两端 （俗称对撞双指针）
循环搜索： 当双指针相遇时跳出；
计算和 s = nums[i] + nums[j]

  • 若 s>target
    指针 j 向左移动，即执行 j=j−1
  • 若 s<target
    指针 i 向右移动，即执行 i=i+1
  • 若 s=target
    立即返回数组 [nums[i],nums[j]]

返回空数组，代表无和为target的数字组合。

正确性证明：

记每个状态为 S(i,j)，即 S(i,j)=nums[i]+nums[j]
假设 S(i,j)<targetS(i, j)，则执行 i=i+1，即状态切换至 S(i+1,j)

  • 状态 S(i,j) 切换至 S(i+1,j) ，则会消去一行元素，相当于 消去了状态集合 {S(i,i+1),S(i,i+2),...,S(i,j−2),S(i,j−1),S(i,j)}
    （由于双指针都是向中间收缩，因此这些状态之后不可能再遇到）。
  • 由于 nums 是排序数组，因此这些 消去的状态 都一定满足 S(i,j)<target，即这些状态都 不是解 。

结论： 以上分析已证明 “每次指针 i 的移动操作，都不会导致解的丢失” ，即指针 i 的移动操作是 安全的；同理，对于指针 j 可得出同样推论；因此，此双指针法是正确的。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            s = nums[i] + nums[j]
            if s > target: j -= 1
            elif s < target: i += 1
            else: return nums[i], nums[j]
        return []

效率

执行用时：148 ms
内存消耗：24.8 MB

来源：

Python LeetCode 简单 对撞双指针

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！