开发者社区> 白头雁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Leetcode 第一题 《两数之和》

简介: 原题目 定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] Leetcode给出了三种解法 暴力法 复杂度O(n^2) 两遍Hash表法,创建Hash表一次O(n),遍历查找O(n) 一遍Hash 一遍Hash算法说明 第一个元素添加到hash表,key是num,value是index。
+关注继续查看

原题目

定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Leetcode给出了三种解法

  • 暴力法 复杂度O(n^2)
  • 两遍Hash表法,创建Hash表一次O(n),遍历查找O(n)
  • 一遍Hash

一遍Hash算法说明

  1. 第一个元素添加到hash表,key是num,value是index。
  2. 计算target - 第二个元素,
    • 如果在Hash表中,遍历结束。命中index(1)和当前元素index(2),返回[1,2]
    • 如果Hash查找没有命中,将2添加到Hash表
  3. 遍历nums数组。

Python 实现

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        dict[nums[0]] = 0
        for i in xrange(1,len(nums)):
            x = nums[i]
            if target-x in dict:
                return (dict[target-x], i)
            dict[nums[i]] = i

评分,战胜99.96%的python提交记录

屏幕快照 2018-07-12 下午12.55.14.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
leetCode刷题 | 两数相加
leetCode刷题 | 两数相加
10 0
《LeetCode刷题》—1.两数之和
《LeetCode刷题》—1.两数之和
16 0
leetcode
在排序数组中查找元素的第一个和最后一个位置
7 0
leetcode第20题
括号匹配问题。 如果只有一种括号,我们完全可以用一个计数器 count ,遍历整个字符串,遇到左括号加 1 ,遇到右括号减 1,遍历结束后,如果 count 等于 0 ,则表示全部匹配。但如果有多种括号,像 ( [ ) ] 这种情况它依旧会得到 0,所以我们需要用其他的方法。 栈! 遍历整个字符串,遇到左括号就入栈,然后遇到和栈顶对应的右括号就出栈,遍历结束后,如果栈为空,就表示全部匹配。
9 0
leetcode第19题
上边我们遍历链表进行了两次,我们如何只遍历一次呢。 看了 leetcode 的讲解。 想象一下,两个人进行 100m 赛跑,假设他们的速度相同。开始的时候,第一个人就在第二个人前边 10m ,这样当第一个人跑到终点的时候,第二个人相距第一个人依旧是 10m ,也就是离终点 10m。 对比于链表,我们设定两个指针,先让第一个指针遍历 n 步,然后再让它俩同时开始遍历,这样的话,当第一个指针到头的时候,第二个指针就离第一个指针有 n 的距离,所以第二个指针的位置就刚好是倒数第 n 个结点。
18 0
「LeetCode」15-三数之和⚡️
「LeetCode」15-三数之和⚡️
39 0
LeetCode 三数之和
本题目主要是更加深化的考察双指针的运用,这里是需要在一个数组中,找到三个数的和为0 的所有三元组,其实可以看作是两个双指针然后最终合并起来,得到一个结果等于期望的值。举一反三如果a + b + c = n , n 是一个传入的变量,解题思路也是一样的。 对于结果集合不能重复的话,我们最常用的方式就是直接通过排序的方式来做,就可以在拿这个数据的时候,直接判断拿过了没有,拿过这个数据就跳过。下面我们就一起来看看具体的题目和解题分析吧
25 0
LeetCode01 - 两数之和
LeetCode01 - 两数之和
40 0
leetcode题解 - 两数之和
leetcode题解 - 两数之和
47 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载