[LintCode 56] Two Sum

### Description

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are zero-based.

https://www.lintcode.com/problem/two-sum/description

Example:

Example1:

Example2:



### Note

1. O(n^2)暴力解法循环枚举所有可能，遇到符合条件的就return
2. 在Hash中添加键值对，通过target减去目标值去索引先前存入Hash中有无符合条件的值O(1),遍历为O(n).

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

### Code

Python3 on LintCode

class Solution:
"""
@param numbers: An array of Integer
@param target: target = numbers[index1] + numbers[index2]
@return: [index1, index2] (index1 < index2)
"""
def twoSum(self, numbers, target):
if numbers is None or len(numbers) == 0:
return [-1, -1]
if target is None:
return [-1, -1]
hash = {}
for i in range(len(numbers)):
if target - numbers[i] in hash.keys():
return [hash[target - numbers[i]], i]
hash[numbers[i]] = i

return [-1, -1]



### Ref Code

class Solution(object):
def twoSum(self, nums, target):
#hash用于建立数值到下标的映射
hash = {}
#循环nums数值，并添加映射
for i in range(len(nums)):
if target - nums[i] in hash:
return [hash[target - nums[i]], i]
hash[nums[i]] = i
#无解的情况
return [-1, -1]


This blog is under a CC BY-NC-SA 3.0 Unported License