LeetCode-1. Two Sum

[ninehills]

20170713

题目

https://leetcode.com/problems/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].

思路

• O(n)的思路其实使用Hash表，只需要查看target - num 对应的数字是否已经遍历过即可
• 实现的时候反向思考了下，在dict中注册了(target -num, value)，代码更加简洁

解答

class Solution(object):
    def twoSum1(self, nums, target):
        """最简单的办法，时间复杂度 O(n^2)
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for k,v in enumerate(nums):
            for i,j in enumerate(nums[k+1:]):
                if v + j == target:
                    return [k, i+k+1]

    def twoSum2(self, nums, target):
        """时间复杂度为 O(n)的办法：Runtime: 76 ms
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for k,v in enumerate(nums):
            if v not in d:
                d[target - v] = k
            else:
                return [d[v], k]