题目描述
给定一个整数数组
nums
和一个整数目标值target
,请你在该数组中找出 和为目标值target
的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:输入:nums = [3,3], target = 6
输出:[0,1]
解题
1.解法一:暴力破解,两for走天下
思路
遍历寻找当前num后与target - num相等的目标元素,返回当前num的下标和目标元素的下标
算法复杂度
时间复杂度:O(n^2),其中 n 是输入数组 nums 的长度。
代码中存在一个外层循环,其循环次数为 n,内层循环也是遍历从当前外层循环索引 i+1 开始的剩余元素,最坏情况下需要遍历 n-1 次。因此,在整体上,循环会进行 n*(n-1)/2 次比较,简化后仍为 O(n^2)。
空间复杂度:O(1)
因为它只使用了常数个额外空间来存储变量 results 和循环中的临时变量 index 和 j。
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for i in range(len(nums)):results = target - nums[i]for index, j in enumerate(nums[i+1:], start=i+1):if results == j:return [i,index]
2.解法二:哈希表来咯
思路
初始化一个空字典 hashtable。
使用 enumerate 函数遍历 nums 列表,这样可以同时获得元素的值 num 和对应的下标 i。
对于每一个 num,检查 target - num 是否已经在 hashtable 中。如果存在,则说明找到了一对和为目标值的数,返回它们的下标 [hashtable[target - num], i]。
若当前 num 的值不在哈希表中,将其作为键存入哈希表,并将下标 i 作为对应的值。
如果循环结束都没有找到满足条件的数对,则返回一个空列表 [ ]。
算法复杂度
时间复杂度:O(n),其中 n 代表数组 nums 的长度。
该算法主要包含一个遍历数组的操作,即遍历整个输入数组 nums,并对每个元素执行一次查找操作。查找操作在哈希表中进行,由于哈希表的查找、插入操作在平均情况下均具有 O(1) 的时间复杂度,所以整个算法的时间复杂度主要取决于遍历数组的时间。
空间复杂度:O(n),其中n代表数组 nums 的长度。主要为哈希表的开销。
def twoSum(nums, target):hashtable = {} for i, num in enumerate(nums):complement = target - numif complement in hashtable:return [hashtable[complement], i]hashtable[num] = i return []