LeetCode-1- Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

简言之,查找给定数组内两个数,使得两数和为给定的target

思路:

  遍历给定数组,用一个哈希表存放已经遍历过的值,key是nums中的值,value是其位置索引。

  对于当前遍历的nums[i],查找哈希表中是否存在target-nums[i],若存在,则返回二者索引,否则将(key=nums[i],value=i)放入哈希表中,继续遍历

时间复杂度:O(n)

python代码如下,已AC:

 1 class Solution(object):
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         dictMap = {}
 9         for index, value in enumerate(nums):
10             if target - value in dictMap:
11                 return [dictMap[target - value] , index ]
12             dictMap[value] = index

提交结果:

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

写一个自定义控件attrs自动生成代码工具

894
来自专栏web前端

JavaScript基础学习--13字符串、查找高亮显示

Demos:   https://github.com/jiangheyan/JavaScriptBase 一、字符串      1、str.length; ...

2126
来自专栏陈树义

4.Redis常用命令:List

  在Redis中,List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样,我们可以在其头部(left)和尾部(right)添加新的元素。在插入...

3429
来自专栏JAVA技术站

java字符流之ByteArrayOutputStream,ByteArrayInputStream

ByteArrayOutputStream流用来字节数组输出流在内存中创建一个字节数组缓冲区,所有发送到输出流的数据保存在该字节数组缓冲区中,默认初始化大小32...

682
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

842
来自专栏SeanCheney的专栏

Python题目

简述函数式编程 在函数式编程中,函数是基本单位,变量只是一个名称,而不是一个存储单元。除了匿名函数外,Python还使用fliter(),map(),red...

47316
来自专栏算法修养

ZOJ 3204 Connect them

Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

2776
来自专栏开发与安全

实现一些字符串操作标准库函数、解决一些字符串问题

一、实现字符串操作标准库函数 (1)、strcpy、strncpy、memmove、memcpy、memset、strlen、strncat 的实现 C++ C...

3139
来自专栏二进制文集

LeetCode 473 Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchstic...

1083
来自专栏小樱的经验随笔

POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

2955

扫码关注云+社区