算法 01：两数之和 —— 暴力枚举和哈希表

发表于 分类于 评论： 字数： 2.6k

开始学习，准备找工作了，所以打算刷一刷算法题，在这里记录做题的思考和一些过程。

题目

题目链接：1. 两数之和

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

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

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

示例 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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n²) 的算法吗？

问题理解

既然要在数组中查找到和为某个值的两个整数，并返回数组下标，那么首先应该查找到这两个整数，然后记录下这两个的下标，最后返回这两个下标。所以要做的有两件事：

  1. 在数组中查找和为某个值的两个整数
  2. 记录下这两个整数在数组中的下标并返回

遇到的一些问题

  1. 如何查找到这两个整数：我目前只能想到枚举法
  2. 关于数组的问题：C# 中的数组怎么声明，赋值，长度怎么表示，是否担心越界
  3. 什么是时间复杂度，O(n²)是什么样的复杂度

初次解题

在问题还没解决之时，我尝试去解题，以下是我的答案：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for(int i = 0;i<nums.length;i++)
        {
            for(int j = i+1;j<nums.length;j++)
            {
                if(nums[i]+nums[j] == target)
                {
                    int[2] arrayIndex = new array(i,j);
                }
            }
        }
    }
}

得到的报错：

Line 3: Char 30: error CS1061: 'int[]' does not contain a definition for 'length' and no accessible extension method 'length' accepting a first argument of type 'int[]' could be found (are you missing a using directive or an assembly reference?) (in Solution.cs) 

Line 5: Char 36: error CS1061: 'int[]' does not contain a definition for 'length' and no accessible extension method 'length' accepting a first argument of type 'int[]' could be found (are you missing a using directive or an assembly reference?) (in Solution.cs) 

Line 9: Char 24: error CS0270: Array size cannot be specified in a variable declaration (try initializing with a 'new' expression) (in Solution.cs) 

Line 9: Char 45: error CS0246: The type or namespace name 'array' could not be found (are you missing a using directive or an assembly reference?) (in Solution.cs) 

Line 2: Char 18: error CS0161: 'Solution.TwoSum(int[], int)': not all code paths return a value (in Solution.cs)

报错分析：

  1. 关于数组长度的表示，并非nums.length
  2. 关于数组的声明，声明时无法指定大小，int[2] numsIndex这样的声明是错误的，赋值也是错的
  3. 方法没有返回值

哎~ 太久没写代码就是会这样忘东忘西的

信息查找与整理

关于数组

数组的声明、初始化与赋值：

  • 声明：datatype[] arrayName，二维数组datatype[,] arrayName，以此类推
  • 初始化：datatype[] arrayName = new datatype[n]，n 代表数组长度
  • 赋值：datatype[] arrayName = new datatype[n]{……}，这样声明可省略写数组长度 n，……代表数组中的数据，也可以简写为datatype[] arrayName = {……}
  • 更简化的写集合式：.Net8 之后，可以使用集合表达式[……]，datatype[] arrayName = [……] ，return [……]

数组长度的表示：C# 中使用属性 Length 来表述数组长度。

时间复杂度

本质：当输入规模 n 增大时，算法执行的基本操作次数的增长趋势。

非具体时间或代码行数，而是关注增长最快的那一项

  • 基本操作：加减乘除、比较、数组 / 哈希访问、核心逻辑判断等
  • 增长最快：当 n → ∞ 时，哪一项占主导增长
    • n² + n → 主导 n²
    • 100n → 忽略系数 → O (n)
  • 大 O 表示法：只保留主导项，去掉系数和低阶项
    • f(n) = n² + 3n + 1 → O(n²)

一般比较如下：

O(1)
< O(log n)
< O(n)
< O(n log n)
< O(n²)
< O(n³)
< O(2ⁿ)
< O(n!) //n!为阶乘1*2*3*4……*(n-1)*n
复杂度 直觉 典型代码
O(1) 常数，不随 n 变化 单条语句、简单赋值
O(log n) 对数，折半 二分查找、每次 n /= 2
O(n) 线性 单循环遍历数组
O(n log n) 排序常见 归并排序、快速排序平均情况
O(n²) 双循环 两数之和暴力解
O(n³) 三重循环 矩阵乘法
O(2ⁿ) 指数 递归生成子集
O(n!) 阶乘 全排列生成

暴力枚举

暴力枚举，也是我初次解题使用的方法，使用双重循环遍历所有数组元素和其他元素进行匹配，以查看是否满足条件。访问单个元素的时间复杂度是 O (1)，一次循环是 O (n)，双重循环就是 O (n) x O (n)，即 O (n²)。

哈希表（HashTable）

哈希表是本质一个数组，通过哈希函数把 Key 换算成整数下标，定位到数组中对应的槽位，再从槽位中找到关联的 Value。实际上是用空间换时间 —— 预先申请比实际元素多的内存，使得查找时可以通过下标直接寻址，省去了逐个比较的遍历过程。

而哈希表存在一个问题叫作哈希冲突（Collision），是由于数组长度有限，不同的键可能会计算出相同的索引。常用解决方法是通过链地址法（槽里挂链表）或开放寻址法（找下一个空槽）来解决。

键值对（Key-Value Pair）

键值对，顾名思义，就是一对数据：

  • 键（Key）：用来查找的标识，必须唯一
  • 值（Value）：与键关联的数据

字典（Dictionary）

C# 中的 Dictionary 其实就是键值对的集合，内部基于哈希表实现，所以按键查找的时间复杂度是 O (1)。

以下是 AI 的回答，我自己对这些底层原理也半知不解，遇到的时候再说了。

在 .NET 中，Dictionary 并没有直接使用传统的 “对象链表”，而是用了两个紧凑的 Int32 数组来管理数据，这种方式对 CPU 缓存更友好：

  • buckets 数组：存储的是索引，指向 entries 数组。
  • entries 数组：存储实际的数据节点，包含：
    • hashCode: 缓存的哈希值（避免重复计算）。
    • next: 冲突时的下一个节点索引（形成一个隐式链表）。
    • key / value: 实际的数据。

关于哈希冲突，Dictionary 在实际情况下影响很小，即使冲突，查找也能接近 O (1)，因为 C# 的 Dictionary 通过数组模拟链解决冲突，配合自动扩容让冲突在实践中几乎不影响性能。所以可以忽略。

除非使用自定义类型作为 Key 时，必须重写必须同时重写 GetHashCode() 和 Equals()这两个方法，否则会出现逻辑 Bug，程序不报错，但查找的结果不对。

另外在重写GetHashCode()时，可以使用HashCode.Combine()，更加安全高效。

最终解题

暴力枚举解法：O (n²)

经过修正后的暴力枚举法
public int[] TwoSum(int[] nums, int target)
{
    for (int i = 0; i < nums.Length; i++)
    {
        for (int j = i + 1; j < nums.Length; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                return [i, j];
            }
        }
    }
    return []; // 题目保证有答案，实际不会走到这里
}

哈希表解法：O (n)

首先，理解题目里的键值对是什么。由于题目是从已知的整数中获取其未知下标，那么 Key 就是整数，Value 就是整数对应的数组下标。

由于使用的是 C#，所以理所当然地使用字典来进行哈希查找。在查找前声明一个键值类型都为int的字典。

然后开始循环：先算出补数complement，使用target减去当前的nums得到。然后比对字典中是否含有这个补数（Key）的对应下标（Value），如果有就返回这个补数和当前数的下标，否则将当前的数作为 Key，当前下标 i 作为 Value 存入到字典中，反复循环直到得到结果位置。

这里要注意，一定要先判断字典中是否存在对应的 Key 再将键值对存入，如果先存入再查，当 nums = [3, 3], target = 6 时，i = 0 的时候，补数等于 3，查找时会找到已经存起来的 i = 0 的数，而不是 i = 1 的数，错误地返回 [0, 0]而不是[0, 1]。先查后存保证了两个数的下标一定不同。

哈希表解法
public int[] TwoSum(int[] nums, int target)
{
    Dictionary<int, int> numDict = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];//complement补数
        if (numDict.ContainsKey(complement))
        {
            return [numDict[complement], i];
        }
        numDict[nums[i]] = i;
    }
    return []; // 题目保证有答案，实际不会走到这里
}

以上哈希表法，经过 AI 的复盘，说：

这段代码在底层会进行两次哈希查找：一次是 ContainsKey 判断是否存在，另一次是 numDict[complement] 获取具体的值。

在 C# 中，更推荐的做法是使用 TryGetValue 方法。它能在判断键是否存在的同时取出对应的值，底层只需要执行一次哈希查找，性能会稍微更好一点点：

更好的方法
if (numDict.TryGetValue(complement, out int index))
{
    return [index, i];
}

这里的out int index是什么呢？

out 是 C# 的输出参数关键字，TryGetValue 会在找到键时，把对应的值（此题中就是补数对应的数组下标）直接写入后面声明的参数int index中，省去了再单独用 numDict[complement] 取值的步骤。

看看 VSCode 中的说明：

bool Dictionary<int, int>.TryGetValue(int key, out int value)

Gets the value associated with the specified key.

返回结果:  
true if the Dictionary<TKey, TValue> contains an element with the specified key; otherwise, false.  
“TryGetValue”在此处不为 null。

异常:  
  ArgumentNullException

写在最后

到这里，这篇文章就结束了。上学的时候算法没认真学，每次涉及到查找的时候只会使用暴力枚举，所以这次的哈希表解法学起来有些废时间，从 4 月 17 日到 19 日凌晨，才完成了这篇文章。虽然大部分内容都是由 AI 给出，但也尽量加入了个人的一些思考，以帮助自己更好的理解所学到的内容。AI 真的帮助了我许多，要是之前学算法的时候有 AI 帮助就好了，虽然有可能会用它来偷懒哈哈哈。