美文网首页
leetcode 1. Two Sum

leetcode 1. Two Sum

作者: 咿呀咿呀呦__ | 来源:发表于2017-12-26 20:34 被阅读0次

    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].
    
    class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            num_maps = {}
            for index, value in enumerate(nums):
                complement = target - value
                complement_index = num_maps.get(complement)
                if complement_index is not None:
                    return [complement_index, index]
                num_maps.update({value: index})
            return []
    

    思路:
    其实很简单,题目已经假定肯定有匹配数字,所以不用考虑其它情况。

    直接搞个dict,每次遍历一个数就把它和它的索引存在里面,然后每次都检查补数在不在dict里面:

    如果在,返回补数索引本次遍历的数字索引

    Complexity Analysis:

    Time complexity : O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.

    Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

    相关文章

      网友评论

          本文标题:leetcode 1. Two Sum

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