LeetCode01：两数之和

1. 两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

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

示例 2：

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

示例 3：

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

题解

（1）暴力枚举

枚举数组中的每一个数x，寻找数组中是否存在target-x。

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self,nums,target):
        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 []

（2）哈希表

对于数组中的每一个数x，首先查询哈希表中是否存在target-x，如果存在则返回结果，不存在就将x插入到哈希表中，保证不会让x和自己匹配。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self,nums,target):
        hashtable = dict()
        for i,num in enumerate(nums):
            num2 = target - num 
            print(num,num2)
            if num2 in hashtable:
                return [i,hashtable[num2]]
            hashtable[num] = i
            print(hashtable)
        return []

知识点

  • 是否会报超出索引异常

    在方法一的双层for循环中，假设nums为5个元素，当for的外层循环遍历到最后一个元素时，i为4，内层循环涉及到for j in range(5,5)，生成的序列将是空的。因此，for j in range(5,5) 实际上不会执行循环体内的任何代码，也不存在报错。在 Python 中，尝试访问超出数组（列表）索引的元素会引发错误。具体来说，如果尝试访问一个不存在的索引位置，Python 会抛出 IndexError 异常。

  • 时间与空间复杂度

    1、使用暴力枚举，时间复杂度为O($n^2$​)，因为需要使用两层循环来检查数组中每对不同的元素，看它们的和是否等于 target；空间复杂度为O(1)，因为除了输入和输出之外，只需要有限的额外空间。

    2、使用哈希表，时间复杂度为O(n)，因为只需要遍历数组一次，对于每个元素，可以在 O(1) 的时间内通过哈希表检查 target - num 是否存在；空间复杂度为O(n)，因为最坏的情况下，可能需要将数组中的所有元素都存储在哈希表中。