LeeCode第一次刷题（两数相加）

佚名 5年前 (2019-02-01) 算法 1803人围观抢沙发百度已收录

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素

举例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路及难点

第一次刷数据结构相关的题目，老实说，内心还是有点小激动的。看到题目第一反应，就是暴力法，直接两个for循环就可以解决。
但想着还是要有点挑战才好，要把时间复杂度降到O(n)才有成就感。直觉应该要用到哈希表辅助才行。
分三种情况：

两个数及它们的差都不同
三个数中有两个相同
三个数都相同

第一种解法我是先保存哈希，然后再对差是否在哈希中做判断，导致多了几个额外的判断逻辑，不够简洁。解法如下：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        record = {}

        for index,num in enumerate(nums): 
            diff = target - num 

            if num in record:
                l = record[num]
                l.append(index)
                record[num] = l
            else:    
                record[num] = [index]
            
            if diff in record and record[diff][0]!=index:
                return[record[diff][0],index]

第二种解决我是参考了Java的解法想到的，在Java中map中的key也是不能重复的（我原以为是可以的，真是低级错误！：），将先判断的逻辑提前，居然可以精减到只用6行代码解决。python果然是够方便的。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        record = {}

        for index,num in enumerate(nums): 
            diff = target - num 

            if diff in record :
                return[record[diff],index]
   
            record[num] = index