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 条评论
登录 后参与评论

相关文章

来自专栏idba

了解Python装饰器

一 装饰器是什么 装饰器是一个用于封装函数或者类的代码工具,显式地将封装器作用于函数或者类上,达到程序运行时动态增加功能的目的。对于函数运行前处理常见前置条件...

1136
来自专栏SeanCheney的专栏

Python题目

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

54016
来自专栏开发与安全

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

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

3219
来自专栏Astropeak

掌握Python 装饰器,其实只需要一盏茶的功夫

1613
来自专栏cloudskyme

设计模式(3)-装扮你的类(装饰模式)

首先看看书上的例子吧!人穿衣服的例子! 类图就不画了,就是简单的类结构。 代码如下: #include <iostream> using namespace ...

2635
来自专栏Android知识点总结

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

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

610. 数对的个数

★★   输入文件:dec.in   输出文件:dec.out 简单对比 时间限制:1 s   内存限制:128 MB Description 出题是一件...

2927
来自专栏web前端

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

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

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

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

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

3045
来自专栏JAVA技术站

java字符流之ByteArrayOutputStream,ByteArrayInputStream

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

842

扫码关注云+社区

领取腾讯云代金券