LeetCode如何找出和为s的两个数字

这篇文章主要为大家展示了“LeetCode如何找出和为s的两个数字”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“LeetCode如何找出和为s的两个数字”这篇文章吧。

创新互联建站专注于网站建设|成都网站维护|优化|托管以及网络推广,积累了大量的网站设计与制作经验,为许多企业提供了网站定制设计服务,案例作品覆盖三轮搅拌车等行业。能根据企业所处的行业与销售的产品,结合品牌形象的塑造,量身定制品质网站。

题目描述

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

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

题目样例

                     

示例

  • 输入:nums = [2,7,11,15], target = 9

  • 输出:[2,7] 或者 [7,2]

  • 输入:nums = [10,26,30,31,47,60], target = 40

  • 输出:[10,30] 或者 [30,10]

                     

题目思考

  1. 如何利用递增排序的条件?
  2. 如何做到空间复杂度是 O(1)?
                     

解决方案

                     
思路
  • 一个比较容易想到的思路是使用一个集合, 然后遍历一遍数组: 如果                         target-当前的数已经在集合的话, 就说明找到了一对结果, 直接返回即可; 否则就把当前的数加入集合
  • 但这个思路没有利用到递增排序的条件, 且使用了额外的空间, 并不是最优解
  • 如何利用排序的条件呢? 通常有两种思路:                         二分或者双指针
  • 这里如果使用二分的话, 意味着固定当前的数为起点, 然后二分查找右侧区间                         target-当前的数是否存在, 会额外引入 logN 的时间复杂度, 还没有上面的思路好
  • 所以尝试使用双指针的做法, 将两个下标 i 和 j 初始化为数组的头和尾, 然后往中间靠拢
  • 根据当前的和, 具体分为以下三种情况:
    1. nums[i] + nums[j] == target: 找到一对满足条件的数字了, 直接返回
    2. nums[i] + nums[j] < target: 当前和小于 target, 因为数组有序, 如果保留 nums[i], 而 j 继续往左的话, 新的和肯定更小于 target, 所以 nums[i]可以被安全排除, 即 i 直接加 1
    3. nums[i] + nums[j] > target: 当前和大于 target, 因为数组有序, 如果保留 nums[j], 而 i 继续往右的话, 新的和肯定更大于 target, 所以 nums[j]可以被安全排除, 即 j 直接减 1
  • 这样遍历下去最终肯定 i 和 j 会相遇, 此时退出循环, 说明没找到满足条件的数字对, 返回空数组即可
  • 使用双指针做法后, 时间复杂度没有变差, 也不需要额外的空间了
                     
复杂度
  • 时间复杂度 O(N): 只遍历了一遍数组
  • 空间复杂度 O(1): 只使用了几个变量
                     
代码
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 双指针
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                # 找到一对满足条件的数字, 直接返回
                return [nums[i], nums[j]]
            elif nums[i] + nums[j] < target:
                # 当前和小于target, 只能是i向右移, 这样后续和才会更大
                i += 1
            else:
                # 当前和大于target, 只能是j向左移, 这样后续和才会更小
                j -= 1
        return []

以上是“LeetCode如何找出和为s的两个数字”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


新闻标题:LeetCode如何找出和为s的两个数字
URL标题:http://ybzwz.com/article/gdjhcc.html