专栏首页木又AI帮打卡群2刷题总结1001——两数之和 II - 输入有序数组

打卡群2刷题总结1001——两数之和 II - 输入有序数组


leetcode第167题:两数之和 II - 输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/


【题目】

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

说明:

返回的下标值(index1 和 index2)不是从零开始的。你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

【思路】

1、暴力解法:两轮for循环,遍历所有可能,时间复杂度太高。

2、双指针:只是两个指针i和j分别指向第一个元素和最后一个元素,不断比较nums[i] +nums[j]和target的大小,并移动指针。如果nums[i] +nums[j] == target,返回结果;如果nums[i] +nums[j] > target,则i后移,使得两数和变大;如果nums[i] +nums[j] < target,则j前移,使得两数和变小。

3、hash:遍历数组,判断target - nums[i]是否存在字典d中,存在则返回结果;不存在则将元素及位置存储在字典中,即d[nums[i]] = i。

【代码】

python版本

双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            # 刚好相等,退出
            if numbers[l] + numbers[r] == target:
                break
            # 和更大,r指针前移
            if numbers[l] + numbers[r] > target:
                r -= 1
            # 和更小,l指针后移
            else:
                l += 1
        
        # 保证有结果,不用再判断是否满足条件
        # 注意,本题返回的下标从1开始
        return [l + 1, r + 1]

hash

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        d = {}
        for i, n in enumerate(numbers):
            if target - n not in d:
                d[n] = i
            else:
                # 注意,本题返回的下标从1开始
                return [d[target - n] + 1, i + 1]
        
        # 保证有结果,可以不用再判断是否满足条件
        return [-1, -1]

【相似题目】

1. 两数之和

方法简述:hash

15. 三数之和

方法简述:排序后,一层for循环+two sum方法

18. 四数之和

方法简述:排序后,两层for循环+two sum方法

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0727——搜索旋转排序数组 II

    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

    木又AI帮
  • 打卡群2刷题总结1003——搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 打卡群刷题总结0726——删除排序数组中的重复项 II

    链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii

    木又AI帮
  • 【小Y学算法】⚡️每日LeetCode打卡⚡️——43. 两数之和 II - 输入有序数组

    给定一个已按照 非递减顺序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。

    呆呆敲代码的小Y
  • 打卡群刷题总结0827——组合总和 II

    链接:https://leetcode-cn.com/problems/combination-sum-ii

    木又AI帮
  • 打卡群刷题总结0620——整数转罗马数字

    链接:https://leetcode-cn.com/problems/roman-to-integer

    木又AI帮
  • 打卡群刷题总结1006——跳跃游戏 II

    链接:https://leetcode-cn.com/problems/jump-game-ii

    木又AI帮
  • 打卡群刷题总结0802——反转链表 II

    方法:得找到第m-1个节点,在翻转m->n链表后,再修改m和m-1位置上节点指针。

    木又AI帮
  • 打卡群刷题总结0630——在排序数组中查找元素的第一个和最后一个位置

    链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-s...

    木又AI帮
  • 力扣题目汇总(两数之和Ⅱ-输入有序数组,删除排序数组中的重复项,验证回文串)

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    小小咸鱼YwY
  • 贪心算法:买卖股票的最佳时机II

    题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

    代码随想录
  • 打卡群刷题总结0605——缺失数字

    链接:https://leetcode-cn.com/problems/missing-number

    木又AI帮
  • 打卡群刷题总结0730——格雷编码

    1、每次新增的数num2[j] = 2^(i-1) + num[-j-1],其中,i为二进制数字的位数,j为数组的第几个数。

    木又AI帮
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新
  • 【LeetCode】贪心算法--买卖股票的最佳时机 II(122)

    为什么要在LeetCode刷题?大家都知道不管是校招还是社招算法题是必考题,而这一部分恰巧是大多数人的短板,所以刷题首先是为了提高自身的编程能力,能够在算法面试...

    PM小王
  • FPGA 之 SOPC 系列(四)NIOS II 外围设备--标准系统搭建

    今天给大侠带来今天带来FPGA 之 SOPC 系列第四篇,NIOS II 外围设备--标准系统搭建,希望对各位大侠的学习有参考价值,话不多说,上货。

    FPGA技术江湖
  • 打卡群刷题总结1003——分割等和子集

    链接:https://leetcode-cn.com/problems/partition-equal-subset-sum

    木又AI帮
  • 打卡群刷题总结0723——组合

    链接:https://leetcode-cn.com/problems/combinations

    木又AI帮
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

    新智元

扫码关注云+社区

领取腾讯云代金券