来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1.暴力遍历法
解题思路:遍历数组,对于当前的元素 nums[i]
,如果 result=taget-nums[i]
在数组中,则返回这 nums[i]
和 result
的下标。如果已经查询元素 nums[i]
的所有配对情况,且没有找到可以构成 target
的了一个元素,则下一次查询从第 i+1
个位置开始。
用到的知识:
-
python
index
方法:
用法:nums.index(result)
含义:获取result
在nums
列表中的下标 -
python
in
关键字
用法:result in nums
含义:判断result
是否在nums
数组中
时间复杂度:对列表使用in关键字的时间复杂度为O(n),对字典和集合使用in关键字的时间复杂度为O(1)
解题代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
result=target-nums[i]
if result in nums[i+1:]:
return [i,nums[i+1:].index(result)+i+1]
复杂度分析:
- 时间复杂度:O(n^2)
Line-3循环3次,Line-5用in判断列表的时间复杂度为O(n),因此时间复杂度为O(n*n)=O(n^2) - 空间复杂度:O(1)
2.哈希表
解题思路:为了降低时间复杂度,可以使用哈希表来进行判断。借助哈希表/字典,每次遍历列表,对于当前的元素nums[i],计算result=target-nums[i]是否存在于字典中。如果存在,则返回result的下标;如果不存在,则将{nums[i]:i}作为字典项存入字典中。使用字典有如下好处:①对字典使用in关键字的时间复杂度为O(1);②判断的同时可以获得result的下标。
解题代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_dict={}
for i in range(len(nums)):
result=target-nums[i]
if result in hash_dict.keys():
return [hash_dict[result],i]
else:
hash_dict[nums[i]]=i
复杂度分析:
- 时间复杂度:O(n)
- 空间复杂度:O(n)
3.题目描述
给定一个整数数组 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]
标签:target,nums,Python,题解,复杂度,int,result,两数,字典
From: https://www.cnblogs.com/venas/p/17346661.html