[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.
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
Example:
Example1:
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].
Example2:
给出 numbers = [15, 2, 7, 11], target = 9, 返回 [1, 2].
Note
- O(n^2)暴力解法循环枚举所有可能，遇到符合条件的就return
- 在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
Update Review
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):
# write your code here
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
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享（BY-NC-SA）：使用者可以对本创作进行共享、演绎，但使用时须进行署名（同时标明是否（对原始作品）作了修改），且不得运用于商业目的，采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接：https://dataleoz.com/lintcode-two-sum/