[LeetCode] Two Sum

题意

在数组 nums 中找到两个不重复的数字 nums[x] 和 nums[y]，使 nums[x]+nums[y]=target。

输出 x 和 y。

数据保证有答案。

题解

应该不难吧。

方法一

我比较崇尚暴力…… 恩。

遍历，t = target - nums[i]，如果 t 也在 nums 中并且 t 的序号不为 i，说明找到了一组解。

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for x in range(len(nums)):
            t = target - nums[x]
            if t in nums:
                pos = nums.index(t)
                if not x == pos:
                    return [x, pos]

结果

16 / 16 test cases passed.
Status: Accepted
Runtime: 848 ms

方法二

为什么方法一那么慢呢？因为 pos = nums.index(t) 这句话耗时比较长，整体程序复杂度为 O(n^2)。

那么。如何把复杂度降下来呢？或者，pos = nums.index(t) 这句话，能不能有什么快速的办法？

字典。Python 的字典。

我们把出现过的数字的位置全部拿字典记录下来。这样就可以用 O(1) 的时间找出某个数字出现的位置。

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        passed = {}
        for ith, x in enumerate(nums):
            t = target - x
            if t in passed and passed[t] != ith:
                return [passed[t], ith]
            else:
                passed[x] = ith

结果

16 / 16 test cases passed.
Status: Accepted
Runtime: 44 ms

桩程序

if __name__ == '__main__':
    cases = [
        {'data': [2, 7, 11, 15], 'target': 9, 'ans': [0, 1]},
        {'data': [0, 0, 1], 'target': 0, 'ans': [0, 1]},
    ]

    for item in cases:
        ans = (Solution()).twoSum(nums=item['data'], target=item['target'])
        print(str(ans == item['ans']) + "\t=>" + str(ans) + ":" + str(item['ans']))