leetcode - Two Sum
leetcode Python-Two Sum

问题描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]

大体意思就是给出一个数组，数组中存在两个数的和为给出的目标和，数组中的数字只能用一次，给出符合要求数的索引值。

Python示例

示例一

class Solution(object):

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        if len(nums) < 2:

            return False

        for firstindex, firstnum in enumerate(nums):   # 遍历数组

            secondnum = target - firstnum
          # 求匹配的值
            nums[firstindex] = "a"
                 # 替换该值，避免影响获取匹配值的索引
            if secondnum in nums:
                  # 判断数组中是否包含匹配值
                secondindex = nums.index(secondnum)
# 获取匹配值的索引
                return [firstindex, secondindex]
   # 返回坐标

该示例运行leetcode的测试代码的时间为699 ms。

替换对应数值，获取匹配值的索引，消耗了时间。

示例二

class Solution(object):

    def twoSum(self, nums, target):

        dict = {}                 # 字典保存对应值的索引

        for i, value in enumerate(nums):

# 遍历数组 if target-value in dict: # 判断匹配值是否在字典中 return (dict[target-value], i) # 如果存在，返回字典中对应索引，和当前索引 dict[value] = i # 将当前值和对应索引保存到字典

该示例运行leetcode的测试代码的时间为346ms。 减少示例一替换和获取索引值的耗时。

by 李鹏