每日算法-两数字之和(two sum)

作者: ifjgm | 来源:发表于2019-05-21 14:31 被阅读0次

描述

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解决方案

使用语言python

class Solution:
    def twoSum(self, nums, target):
        for i, val in enumerate(nums):
            another=target-val
            try:
                p_another=nums.index(another,i+1,len(nums))
            except ValueError:
                continue
            else:
                return [i,p_another]

思路

  • 遍历数组,将目标值和数组中的元素之间的差值
  • 从list的当前元素位置的后面一位开始找与差值元素相等的数,若不存在,则会报错 ValueError,那么就结束当前循环,继续下一轮循环。若存在则,返回当前元素位置和差值元素位置

重点

  • 从list的当前元素位置的后面一位开始查找,差值元素是否存在。首先能防止使用两个相同元素,第二减少复杂度,因为前面的元素肯定是使用过的,不需要再查找。
  • 报错就继续下一个循环
  • 找到正确的元素位置后就返回,结束整个遍历。

测试用例

nums=[3,2,4] ,target=6 #重复利用元素的算法,无法通过

相关知识点参考文档或博客

相关文章

网友评论

    本文标题:每日算法-两数字之和(two sum)

    本文链接:https://www.haomeiwen.com/subject/moqjzqtx.html