Leetcode1 两数之和 python两种方法实现

Leetcode1 两数之和 python两种方法实现

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

分析：给定一个目标数值，需要返回和为目标数值的两个数的下标，而且答案只有一个。即对于a+b = target， 有且只有一个解。

方法一：枚举法（暴力解法）

对于一个数组[c1,c2,c3,c4,c5], 可以一组一组的判断，即(c1,c2),(c1,c3),(c1,c4),(c1,c5),

(c2,c3),(c2,c4),(c2,c5)

(c3,c4),(c3,c5),

(c4,c5)

即枚举法。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums) # 获取数组的长度
        for i in range(n):
          for j in range(i+1,n):
            if(nums[i]+nums[j] == target):
              return [i,j]
        return []
          

时间复杂度O(n^2), 空间复杂度O(1), 因为只使用了3个临时变量,n, i,j.

分析：时间复杂度很高，空间复杂度很低。如何能够降低时间复杂度，一种思路是用空间换时间。

方法二：用空间换时间。

我们还是来看枚举法：

(c1,c2),(c1,c3),(c1,c4),(c1,c5),

(c2,c3),(c2,c4),(c2,c5)

(c3,c4),(c3,c5),

(c4,c5)

大部分时间花在了寻找第二个数上。有一个基本的观察是：如果第二个数与第一个数的和为目标数值，那么目标数值减去第二个数一定存在于数组中。

快速查找数值的结构是哈希集合或者哈希表，python中对应的结构是dict.

第一遍遍历的时候，如果当前数为答案中的第二个数，则target-当前数 则一定位于当前数之前的数组成的哈希集合中。
使用一个叫做dict的数据结构，键为数，值为当前数的索引。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()
        for i, num in enumerate(nums):
          if(target - num in hashtable):
            return [i, hashtable[target-num]]
          hashtable[num]= i

时间复杂度 O(n), 空间复杂度O(n)

结果：

链接：

https://leetcode.cn/problem-list/array/

从这一期leetcode开始，我会经常回来看我的博客，如果博主们觉得哪里看不懂，欢迎随时在评论区提出。

刷Leetcode就如同刷象棋路边摊一样，最开始刷的时候，觉得某一个象棋的路数好奇妙，刷着刷着回过头来看时发现那个招数在自己的眼中变得没那么令人惊讶了，变得稀松平常了。