题目描述
题目
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:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
思路
信息解读
- one solution: 第一次找到就可
- not use twice: 不会有重复的元素？不会自己相加？（不够清楚）
解题步骤
- 用一个dict 保存 数组中的元素和索引，然后最多只用遍历一次 nums
- dict 查找：O(1)
- 时间复杂度O(n)
- temp = target - 当前数组遍历值
- 在dict 查找 temp,如果有 返回[dict[temp], nums[i]], 如果没有加入当前遍历的数及其索引
coding
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 用dict 存储 元素与索引 因为dict查找的复杂度是1 遍历一遍就够
dict1 = {}
for i in range(len(nums)):
temp = target - nums[i]
if temp in dict1:
return [dict1[temp], i]
else:
dict1[nums[i]] = i
- 参考与推荐
leetcode 动画展示
多种解法，优化
