题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

DEMO

1
2
3
4
5
> 给定 nums = [2, 7, 11, 15], target = 9
>
> 因为 nums[0] + nums[1] = 2 + 7 = 9
> 所以返回 [0, 1]
>

解法

暴力破解

两层循环遍历所有数进行比对

  • 时间复杂度:$T(n)=\frac{n^2-1}{2}$;$O(n)=n^2$
  • 空间复杂度:$S(n)=3$;$O(n)=1$
  • LeetCode结果6436ms/12.5MB
1
2
3
4
5
def twoSum(nums, target):
for i in range(len(nums)-1):
for j in range(len(nums)):
if nums[i] + nums[j] == target:
return i, j

暴击破解改进

由于原始的暴力破解需要对每一个前数计算后续的所有后数,现在优化为计算出每一个前数需要的后数,校验是否在nums

  • 时间复杂度:$O(n)=n$
  • 空间复杂度:$O(n)=1$
  • LeetCode结果:828ms/12.5MB
1
2
3
4
5
def twoSum(nums, target):
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

建立HASH表–实际就是键值对

由于每次都去原数组中查找很费时间,而且还存在重复的元素,可以对每一个独一无二的元素简历一个索引值。简单说就是字典查找比列表快。

  • 时间复杂度:不会算
  • 空间复杂度:$0(n)=n$
  • LeetCode结果:48ms/13.1MB
1
2
3
4
5
6
7
8
9
def twoSum(nums, target):
nums_dict = {}
for index, item in enumerate(nums):
result = target - item

if result in nums_dict and nums_dict[result] != index:
return [nums_dict[result], index]
else:
nums_dict[item] = index
相关文章
评论
分享
  • findMedianSortedArrays

    题目 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 DEMO ...

    findMedianSortedArrays
  • lengthOfLongestSubstring

    题目 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 DEMO 输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 输入: “bbbbb”输出: 1解释: 因...

    lengthOfLongestSubstring