(【力扣-Python】1、两数的和)
题目
题目：两数之和。
难度：简单。
给定一个整数数组 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]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
**进阶：**你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
Related Topics
数组
哈希表
???? 16228
???? 0
思路
解题之前确定两个前提：
1、题目是正确的，答案一定存在，不会不存在答案，且只有一个答案
2、数组中同一个元素在答案里不能重复出现，则表明如果target = 2 * x，那么nums中要么就存在两个x，要么答案就不会选x
时间复杂度
语句总的执行次数T(n)是关于问题规模n的函数。
随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。
算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。
常用的时间复杂度所耗费的时间从小到大依次是 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
解题
初级，O(n^2)
题目中说：
**进阶：**你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
那么意味着，有一种时间复杂度等于 O(n^2) 的算法。
对于列表中的元素个数是n，对列表进行嵌套的两次循环，时间复杂度就是 O(n^2)。
通过对nums进行嵌套循环是可以实现功能的，代码如下：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if ((target // 2) * 2 == target) and ((target // 2) in nums) and nums.count(target // 2) == 2:
i = nums.index(target // 2)
nums.reverse()
j = len(nums) - nums.index(target // 2) - 1
return [i, j]
# O(n^2)
for i in range(len(nums)):
for j in range(len(nums)):
if i != j and nums[i] + nums[j] == target:
return [i, j]
提交执行，效果并不理想，耗时太长。
> 2023/02/03 10:42:07
Success:
Runtime:5380 ms, faster than 5.02% of Python online submissions.
Memory Usage:14 MB, less than 21.70% of Python online submissions.
进阶
按照题目要求，想出一个时间复杂度小于 O(n^2) 的算法。
1，O(nlogn)
二分查找法的时间复杂度是O(nlogn) ，要做二分查找，需要先对nums进行排序。
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if ((target // 2) * 2 == target) and ((target // 2) in nums) and nums.count(target // 2) == 2:
i = nums.index(target // 2)
nums.reverse()
j = len(nums) - nums.index(target // 2) - 1
return [i, j]
num1 = []
for num in nums:
num1.append(num)
num1.sort()
# O(nlogn)
for i in range(len(num1)):
left = i + 1
right = len(num1)
while left < right:
mid = (right - left) // 2 + left
sum = num1[mid] + num1[i]
if sum == target:
return [nums.index(num1[i]), nums.index(num1[mid])]
elif target > sum:
left = mid + 1
else:
right = mid
提交执行，提升效果明显。
> 2023/02/03 12:00:07
Success:
Runtime:44 ms, faster than 68.38% of Python online submissions.
Memory Usage:13.5 MB, less than 89.59% of Python online submissions.
2，O(n)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if ((target // 2) * 2 == target) and ((target // 2) in nums) and nums.count(target // 2) == 2:
i = nums.index(target // 2)
nums.reverse()
j = len(nums) - nums.index(target // 2) - 1
return [i, j]
# O(n)
dict = {}
l = len(nums)
for i in range(0, l):
dict[nums[l-i-1]] = l-i-1
if dict.has_key(target - nums[i]):
return [dict[target - nums[i]], i]
dict[nums[i]] = i
提交执行，效果还不错。
> 2023/02/03 14:05:50
Success:
Runtime:12 ms, faster than 99.28% of Python online submissions.
Memory Usage:13.5 MB, less than 85.75% of Python online submissions.
多执行几次，还可以更快，但是空间占的就比较多了。
空间复杂度
空间复杂度是对一个算法在运行过程中占用内存空间大小的量度，记做S(n)=O(f(n))。
空间复杂度是考虑程序运行时占用内存的大小。