两数之和

难度:简单1

描述

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

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

示例:

例子

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

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

题解

暴力法

暴力法很简单,遍历每个元素 x,并查找是否存在一个值与 target - x 相等的目标元素。

实现

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
            let num = target - nums[i]
            for j in 0..<nums.count {
                if i == j {
                    continue
                }
                if nums[j] == num {
                    return [i, j]
                }
            }
        }
        return [-1, -1]
    }
}
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        count = len(nums)
        for i in range(count):
            num = target - nums[i]
            for j in range(count):
                if i == j:
                    continue
                if nums[j] == num:
                    return [i, j]
        return [-1, -1]

复杂度分析

  • 时间复杂度:O(n^2),

    对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n) 的时间。因此时间复杂度是 O(n^2)

  • 空间复杂度:O(1)

警告

实际运行的时候,python3 的实现可能跑不通,超过时间限制了!

两遍哈希表

为了对运行时间复杂度进行优化,我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在,我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么?哈希表。

通过以空间换取速度的方式,我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的,它支持以 近似 恒定的时间进行快速查找。用“近似”来描述,是因为一旦出现冲突,查找用时可能会退化到 \overline{O(n)}。但只要你仔细地挑选哈希函数,在哈希表中进行查找的用时应当被摊销为 \overline{O(1)}

一个简单的实现使用了两次迭代。在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素 (target - nums[i]) 是否存在于表中。

注意

该目标元素不能是 nums[i] 本身!

实现

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var hashmap = Dictionary<Int, Int>()
        for i in 0..<nums.count {
            hashmap[nums[i]] = i
        }
        for i in 0..<nums.count {
            if let index = hashmap[target - nums[i]], i != index {
                return [i, index]
            }
        }
        return [-1, -1]
    }
}
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, v in enumerate(nums):
            hashmap[v] = i
        for i, v in enumerate(nums):
            if (target - v) in hashmap:
                index = hashmap[target - v]
                if index != i:
                    return [i, index]
        return [-1, -1]

复杂度分析

  • 时间复杂度:O(n)

    把包含 n 个元素的列表遍历两次,由于哈希表将查找时间缩短至 O(1) ,所以时间复杂度是 O(n)

  • 空间复杂度:O(n)

    所需的额外空间取决于哈希表中存储元素的数量,表中存储了 n 个元素。

一遍哈希表

实际上,我们可以执行一次迭代,在将元素 nums[i] 添加到哈希表的过程中,同时检查当前哈希表中是否有键 (target - nums[i]),如果存在就返回对应键的值和当前索引作为结果。

实现

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var hashmap = [Int: Int]()
        for index in 0..<nums.count {
            let value = nums[index]
            if let i = hashmap[target - value] {
                return [i, index]
            }
            hashmap[value] = index
        }
        return [-1, -1]
    }
}
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for index, value in enumerate(nums):
            if (target - value) in hashmap:
                return [hashmap[target - value], index]
            hashmap[value] = index
        retrun [-1, -1]

复杂度分析

  • 时间复杂度:O(n)

    把包含 n 个元素的列表遍历一次,在哈希表中查找时间只花费 O(1) ,所以时间复杂度是 O(n)

  • 空间复杂度:O(n)

    所需的额外空间取决于哈希表中存储元素的数量,表中存储了 n 个元素。