相信每个想刷leetcode的人,第一次打开网站,就从这道题开始的。
一起起航吧,Great Voyage.
1. 两数之和:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
例如:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum/
Link:https://leetcode.com/problems/two-sum/
哈希
O(N)
遍历数组
如果在字典找到数字,则输出[字典下标,当前下标]
找不到答案,把当前的值放入字典(val -> index)
因为题目说有且只有一组答案,所以不用判断数组为空,返回值不存在的情况
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = dict()
for i in range(len(nums)):
val = target - nums[i]
if val in map:
return [map[val], i]
else:
map[nums[i]] = i
双指针
O(N*logN)
如果题目要求返回两个具体数字,可以先排序,然后使用双指针(start, end)
res = nums[start] + nums[end]
如果res < target, 则说明nums[start] + 最大的数都小于target, start的值太小了,应该start++
如果res > target, 则说明nums[end] + 最小的数都大于target, end的值太大了,应该end–
如果res = target, 则输出答案
class Solution(object):
def twoSum(self, nums: List[int], target: int) -> List[int]:
start = 0
end = len(nums) - 1
nums.sort()
while(start < end):
res = nums[start] + nums[end]
if res == target:
return (nums[start], nums[end])
elif res < target:
start += 1
else:
end -= 1
–End–