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.

版本1:O(n^2)  【暴力 原始版本】O(1)

  1. classSolution(object):
  2. def twoSum(self, nums, target):
  3. length = len(nums)
  4. for i in range(length):
  5. for j in range(i+1,length)://游标后移
  6. if nums[i]+ nums[j]== target:
  7. return[i,j]

版本2:O(n^2)  【暴力 枚举函数增强】O(1)

  1. classSolution(object):
  2. def twoSum(self, nums, target):
  3. for index , item in enumerate(nums):
  4. for past_index , past_item in enumerate(nums[index+1:],index+1):
  5. if item + past_item == target:
  6. return[index, past_index]

版本3:O(n)    【双程hash table】O(n)

  1. classSolution(object):
  2. def twoSum(self, nums, target):
  3. dd = dict()
  4. for index , value in enumerate(nums):
  5. dd[value]= index
  6. for index , value in enumerate(nums):
  7. tt = target - value
  8. if dd.has_key(tt)and dd[tt]!= index:
  9. return[index , dd[tt]]

版本4:O(n)    【单程hash table】O(n)

Python

  1. classSolution(object):
  2. def twoSum(self, nums, target):
  3. dd = dict()
  4. for index , value in enumerate(nums):
  5. tt = target - value
  6. if dd.has_key(tt)and dd[tt]!= index:
  7. return[dd[tt],index]
  8. else:
  9. dd[value]= index

Java

  1. public int[] twoSum(int[] nums, int target){
  2. Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  3. for( int i=0;i<nums.length;i++){
  4. if(!map.containsKey(target - nums[i])){
  5. map.put(nums[i], i );
  6. }else{
  7. int[] rs ={ map.get(target-nums[i]), i };
  8. return rs;
  9. }
  10. }
  11. return nums;
  12. }

1.enumerate内置函数的使用(枚举函数)---用于既要遍历索引又要遍历元素;可以接收第二个参数用于指定索引起始值。

时间: 03-26

1. Two Sum【数组|哈希表】的相关文章

[LeetCode] #1# Two Sum : 数组/哈希表/二分查找

一. 题目 1. Two SumTotal Accepted: 241484 Total Submissions: 1005339 Difficulty: Easy 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 solutio

哈希表--扩展数组

pre-situation: 当哈希表变得太满时候.一个选择是扩展数组. java中数组有固定大小.而且不能扩展.编程时.只能另外创建一个更新的更大的数组.然后把旧数组的所有内容插入 新数组当中. 注意: 哈希函数根据数组大小计算给定数据项的位置. 所以这些数据项不能再放在新数组中和原有数组相同的位置上. 因此不能简单地从一个数组向另一个数组拷贝数据. 扩展后的数组容量通常是原来的两倍.实际上.因为数组容量应该是一个质数. 所以新数组要比两倍的容量多一点.

4.PowerShell -- 数组,哈希表

1. PowerShell数组 声明数组 [email protected]("user1","user2","user3") 查看数组 $strUsers PS C:\Users\Administrator> $strUsers[0] user1 赋值 $strUsers[1]="marui" 重新查看数组元素 PS C:\Users\Administrator> $strUsers user1 marui us

Exchange 2013 PowerShell数组和哈希表

示例: 你可以使用一个变量来存放一个数组,通过这个数组对变量分配多个值,在值之间,值需要用分隔号隔开,下面来创建一个示例: $servers = "EX1","EX2","EX3" 创建一个空的哈希表,可以使用如下语法: $hashtable = @{} 创建完哈希表后,我们可以对它进行赋值: $hashtable["server1"] = 1 $hashtable["server2"] = 2 $hash

poj 3349 数组的hash(最常用、最普通的哈希表建立)

http://poj.org/problem?id=3349 Description You may have heard that no two snowflakes are alike. Your task is to write a program to determine whether this is really true. Your program will read information about a collection of snowflakes, and search

wikioi 1051哈希表

题目描述 Description 给出了N个单词,已经按长度排好了序.如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙). 你的任务是:对于输入的单词,找出最长的龙. 输入描述 Input Description 第一行为N(1<=N<=105).以下N行每行一个单词(由小写组成),已经按长度排序.(每个单词长度<50) 输出描述 Output Description 仅一个数,为最长的龙的长度. 样例输入 Sample Input 5 i a int a

哈希表的基本操作

散列(hash)表/哈希表 1.关键字和和存储的地址建立一个对应的关系:Add = Hash(key): 2. 解决冲突方法: (1)开放定址法 – 探测方式:线性探测.二次探测. (2)再哈希法 (3)分离链接法 – 利用链表的方式. (4)公共溢出区法 3.存储结构:用顺序存储来构建哈希表.构建结构数组 注意:使用不同的哈希函数得到的冲突次数不同. ---------------------------------------------------------------------- 除

hdu 5183. Negative and Positive (哈希表)

Negative and Positive (NP) Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2177    Accepted Submission(s): 556 Problem Description When given an array (a0,a1,a2,?an−1) and an integer K, you are

哈希表

哈希表支持的一种最有效的检索方法:散列. 由于计算哈希值和在数组中进行索引都只消耗固定时间,因此哈希表的最大亮点在于他是一种运行时间在常量级的检索方法. 哈希表主要有两种: 1.链式哈希表:将数据存储在桶中的哈希表,每个桶里面都是一个链表,且链表的容量随着冲突的增大而增大.(换句话说就是如果有冲突,会在桶中的链表加上一个存储的值) 2.开地址哈希表:将数据存在表本身,而不是在桶中,他通过各种探查方法来避免冲突. 解决冲突: 不管在以上那种哈希表中,我们的目标是尽可能均匀的分配表中的元素.所以我们