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]

评论

暂无评论