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, and you may not use the same element twice.
Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析

  • 输入:给定一个整数数组和一个目标值
  • 任务:在数组中找出两个数,使得和等于目标值
  • 条件:假设有且只有一对可行解,且一个数不能使用两次
  • 输出:两个数的下标

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def twoSum(self, nums, target):
# if len(nums) <= 1:
# return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
def test():
nums = [1,2,3,5,6,7]
target = 3
print(self.twoSum(nums, target))

解释

这里一定要注意题目已经假设只会有一个解,遍历数组时用一个字典记录一下目标值和每次遍历到的数的差值,并且存放此时的下标(此下标就是下次遍历时互补值的下标)。每次遍历时判断一下字典中是否存在互补的值,存在则输出

扩展

如果更改题目中的条件,假设存在多对可行解的话,算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def twoSum(self, nums, target):
results = []
if len(nums) >= 1:
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
results.extend([[x, i] for x in buff_dict[nums[i]]])
else:
if target - nums[i] in buff_dict:
buff_dict[target - nums[i]].append(i)
else:
buff_dict[target - nums[i]] = [i]
return results
def test():
nums = [1,2,3,4,5,6,7]
target = 8
print(self.twoSum(nums, target))