LeetCode题目（Python实现）：两数之和

一时失言乱红尘 2023-07-07 11:06 13阅读 0赞

### 文章目录 ###

*  题目
 *   *  自己的想法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  哈希表法
     *   *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例** :

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

## 自己的想法 ##

### 算法实现 ###

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            j = len(nums)
            for i in range(j):
                t = target - nums[i]
                if t in nums[i + 1:]:
                    return [i, nums.index(t, i + 1)]
                else:
                    continue

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 868 ms, 在所有 Python3 提交中击败了36.49%的用户  
**内存消耗** : 14.1 MB, 在所有 Python3 提交中击败了68.74%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n^2)，  
    我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找花费O(n)的时间。
 *  空间复杂度：O(n)，  
    所需的额外空间取决于range中存储的元素数量，最多需要存储 n 个元素。

## 哈希表法 ##

class Solution:
        hashmap = {
        }
            for index, num in enumerate(nums):
                if target - num in hashmap:
                    return [index, hashmap[target - num]]
                hashmap[num] = index

### 执行结果 ###

![20200222184027863.png][]

### 复杂度分析 ###

*  时间复杂度：O(n)，  
    我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
 *  空间复杂度：O(n)，  
    所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

## 小结 ##

先按照自己的想法设计，通过判断`target - nums[i]`是否存在于后面的列表中来找到另一个数字，算法并不是很快。之后学习了哈希表法，通过建立字典，将键与num1匹配，值与num1的索引匹配，一边遍历数组，一边查找并将键值加入字典中，由于哈希表查找时间复杂度低，所以会快很多。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222181418145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20200222184027863.png]: https://img-blog.csdnimg.cn/20200222184027863.png