LeetCode-1.Two Sum

发布于 2017-07-11 05:20:38

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].

这个题目是查找列表中相加为target的两个数。 刚开始做的时候用了两层的for循环也就是说复杂度是N^2,最终Time Limit Exceeded,显然系统不接受N^2复杂度的算法,于是想,如何才能降低复杂度,循环一次就可以找到。这时候想到,遍历一次的过程中target-num,判断相减之后的值在不在nums里面就可以了。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for x,num_a in enumerate(nums):
            y = target - num_a
            if y in nums:
                if nums.index(y) == x:
                    continue
                else:
                    return [x, nums.index(y)]