1.两数之和

一、问题描述

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

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

示例：

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

二、方案一：暴力法

1、思路

暴力法是最直观的方法。通过遍历数组中的每一个数 x，并查找是否存在一个值与 target - x 相等的目标元素。

2、代码实现

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[j] == target - nums[i] {
                return []int{i, j}
            }
        }
    }
    return nil
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组中的元素数量。最坏的情况下可能需要对每个元素进行 n-1 次比较。
• 空间复杂度：O(1)，因为只使用了常数级别的额外空间

三、方案二：哈希表法

1、思路

在方案二的基础上，我们可以进行一些优化。我们可以在遍历数组的同时建立哈希表，这样只需要遍历一次数组。对于每个元素 x，我们首先检查 target - x 是否在哈希表中，如果不在，我们将它加入哈希表。

2、代码实现

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, ok := numMap[complement]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组中的元素数量。我们只遍历了一次数组。
• 空间复杂度：O(n)，我们需要一个哈希表来存储数值到索引的映射。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n^2)	O(1)	实现简单	效率低
哈希表法	O(n)	O(n)	效率高，只需遍历一次	需要额外空间
推荐使用一遍哈希表法，因为它在时间和空间效率上都较为优秀。