LeetCode 1. 两数之和
文章目录
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
最开始想到暴力解法,但是时间复杂度太高了,O(n^2);每次访问一个元素后,也可以得到target - current 的差值,判断差值是不是在列表里即可,利用这个遍历一次就可以得到结果
class Solution:
def twoSum(self, nums, target):
for i in range(len(nums)):
first = nums[i]
second = target - first
if second in nums[i+1:]:
# 判断差值是否在i后的子列表中
# 若存在,获取在子列表中的索引并拼接以获取nums中的索引
j = nums[i+1:].index(second) + i + 1
return [i, j]
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论