TwoSum

题目

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

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

DEMO

给定 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
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
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
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


  转载请注明: Tomorrow TwoSum

 上一篇
addTwoNumbers addTwoNumbers
题目 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,
2019-05-31
下一篇 
自动化测试策略 自动化测试策略
测试系统需求分析 任何测试的基础都是被测系统的功能。手工与非手工测试都是以系统功能为出发点。 确定是否满足自动化测试的前提条件: 项目周期及体量是否达到需要使用自动化 确定是否有足够的技术实现自动 确定测试的范围(模块)以及需要覆盖的
2019-04-17
  目录