题目地址:https://leetcode.com/problems/two-sum/description/

题目描述

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

一种思路是暴力法,用两层for循环,外层for循环遍历nums数组中的每一个元素x,内层for循环遍历x元素后面的元素,并判断其中是否有一个元素的值与target-x相等,如果有,将这两个元素返回。

第二种思路是用一层for循环遍历nums数组中的元素x,令k = target-x,用in判断k是否在nums数组中,如果在,返回x和k

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
k = target - nums[i]
if k in nums and i != nums.index(k):
index = nums.index(k)
return [i,index]

第10行,i != nums.index(k)是为了防止nums=[3,3], target=6这样的情况,需要过滤掉k和nums[i]处在同一个位置。

第二种思路还有另一种实现方法,通过字典构建一个哈希表:

1
2
3
4
5
6
7
8
class Solution:
def twoSum(self, nums, target):
dic = {}
for i,num in enumerate(nums):
if num in dic:
return [dic[num],i]
else:
dic[target-num] = i

在Discuss区还看到一种清奇的实现方法,代码地址

1
2
3
4
5
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)-1,0,-1):
if target-nums[i] in nums[:i]:
return [nums.index(target-nums[i]),i]