引言：为什么需要学习算法？

你可能也发现，即使是社招，面试官也时不时会抛出几道算法题，从简单的反转链表到复杂的动态规划。这常常让人感到困惑：我一个做游戏开发的，写好 Unity 的 C# 代码，实现好游戏逻辑就行了，为什么还要去死磕这些“看似”与游戏开发不沾边的算法题呢？

答案是：面试官考察的不是你背下了多少道题，而是你解决问题的思维方式和代码质量。

逻辑思维能力： 算法题往往需要你分解问题、抽象模型、设计解决方案，这和你在 Unity 中设计游戏系统、优化渲染流程的思维是相通的。
代码实现能力： 算法题要求你把想法清晰、高效地转化为代码，考察你对数据结构和基本语法的掌握程度。
分析和优化能力： 算法的精髓在于找到最优解。面试官希望看到你不仅能写出能跑的代码，还能分析它的效率瓶颈，并提出优化方案。这直接关系到游戏运行时的性能，比如一个寻路算法的效率就可能决定你的 AI 是流畅行动还是卡顿不堪。
学习和适应能力： 算法和数据结构是计算机科学的基石。掌握了这些基础，你就能更快地理解新的技术、新的框架，更好地适应不断变化的开发需求。

本系列教程的目的，就是帮助你从零开始，系统地理解经典算法题的解题思路，掌握那些能揭示一种通用模式而非仅仅是死记硬背的题目。我们将从最基础的复杂度分析和数组开始，一步步揭开算法的神秘面纱。

时间复杂度：衡量算法效率的标尺

当我们在编写代码时，我们不仅仅要考虑它能否解决问题，还要关注它解决问题的效率。效率，通常通过时间复杂度和空间复杂度来衡量。

什么是时间复杂度？

时间复杂度（Time Complexity）是衡量一个算法执行时间随输入规模增长而增长的趋势。它不是指算法执行的具体时间（因为这受到计算机硬件、编程语言、编译器等多种因素影响），而是指随着输入数据量 N 的增大，算法执行语句的总次数是如何变化的。

我们通常使用大 O 标记法（Big O Notation）来表示时间复杂度。它表示的是算法执行时间的上界，即最坏情况下的时间增长趋势，它会忽略常数项和低阶项，只保留最高阶项。

为什么忽略常数项和低阶项？

因为当 N 足够大时，最高阶项对算法运行时间的影响是决定性的。例如，2N2+100N+500 和 N2，在 N=10000 时，N2 已经远大于 100N+500 了。所以我们只关心最高次幂的项。

常见时间复杂度分析

以下是几种常见的时间复杂度，从高效到低效排列：

O(1)：常数时间复杂度
- 无论输入规模 N 多大，算法执行的步数总是固定的。
- 示例： 访问数组中的任意元素、哈希表中插入/查找（平均情况）。
  
  C#
```
int[] arr = {1, 2, 3, 4, 5};
int value = arr[2]; // 直接通过索引访问，一步到位
```
O(logn)：对数时间复杂度
- 算法的执行时间与输入规模的对数成正比。通常通过“折半”的方式来减少问题规模。
- 示例： 二分查找（Binary Search）。每次搜索都将问题规模减半。
  
  C#
```
// 假设在一个有序数组中查找某个值
// 每次查找范围缩小一半，直到找到或范围为空
// log2(N) 次操作
```
O(n)：线性时间复杂度
- 算法的执行时间与输入规模 N 成正比。通常涉及对输入数据进行一次遍历。
- 示例： 遍历数组、查找无序数组中的最大值。
  
  C#
```
// 遍历数组中的所有元素
for (int i = 0; i < n; i++) {// ...
}
```
O(nlogn)：线性对数时间复杂度
- 常见的“高效”排序算法的时间复杂度，如归并排序（Merge Sort）和快速排序（Quick Sort）。通常是 N 次对数操作的组合。
- 示例： 归并排序，每次将数组对半分（logn 层），每层合并操作需要 O(n) 时间。
O(n2)：平方时间复杂度
- 算法的执行时间与输入规模 N 的平方成正比。通常涉及嵌套循环，外层循环 N 次，内层循环也 N 次。
- 示例： 冒泡排序（Bubble Sort）、选择排序（Selection Sort）、两层嵌套循环遍历二维数组。
  
  C#
```
// 两层嵌套循环
for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// ...}
}
```
O(2n)：指数时间复杂度
- 算法的执行时间随输入规模 N 的增长呈指数级增长。通常出现在递归问题中，且存在大量重复计算（未优化）。
- 示例： 未优化的斐波那契数列递归计算、某些穷举搜索问题。这种复杂度通常无法接受。
O(n)：阶乘时间复杂度
- 算法的执行时间随输入规模 N 的增长呈阶乘级增长。最差的复杂度，几乎只出现在穷举所有排列组合的问题中。
- 示例： 旅行商问题（Traveling Salesman Problem）的暴力解法。

如何分析一段代码的时间复杂度？

关注循环： 循环的次数是影响复杂度的主要因素。
- 如果循环次数是常数，则 O(1)。
- 如果循环次数与 N 成正比，则 O(N)。
- 如果有多层嵌套循环，复杂度是各层循环次数的乘积。
关注递归： 递归的深度和每次递归调用的次数决定了复杂度。
关注分支： 条件语句（if/else）不增加复杂度（除非分支内部包含循环或递归）。
忽略常数和低阶项： 例如 O(2N) 简化为 O(N)，O(N2+N) 简化为 O(N2)。

举例分析：

// 例子1: O(1)
int Sum(int a, int b) {return a + b; // 只有一步操作
}// 例子2: O(n)
void PrintArray(int[] arr) {for (int i = 0; i < arr.Length; i++) { // 循环 N 次Console.WriteLine(arr[i]);}
}// 例子3: O(n^2)
void MatrixMultiply(int[,] matrixA, int[,] matrixB) {int n = matrixA.GetLength(0);for (int i = 0; i < n; i++) {       // 外层循环 N 次for (int j = 0; j < n; j++) {   // 内层循环 N 次// ... 常数操作}}
}// 例子4: O(log n)
int BinarySearch(int[] arr, int target) {int left = 0;int right = arr.Length - 1;while (left <= right) { // 循环次数取决于每次对半分的次数int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}

空间复杂度：衡量算法内存消耗的标尺

**空间复杂度（Space Complexity）**是衡量一个算法在执行过程中临时占用存储空间大小的趋势。它同样用大 O 标记法表示。

O(1)：常数空间复杂度
- 算法执行所需的额外空间不随输入规模 N 变化。
- 示例： 只使用少量变量的计算。
O(n)：线性空间复杂度
- 算法执行所需的额外空间与输入规模 N 成正比。
- 示例： 创建一个与输入数组大小相同的辅助数组。
O(n2)：平方空间复杂度
- 算法执行所需的额外空间与输入规模 N 的平方成正比。
- 示例： 创建一个 NtimesN 的二维数组。

如何分析空间复杂度？

变量： 声明的变量通常占用常数空间。
数据结构： 算法中使用的额外数组、链表、哈希表等数据结构所占空间。
递归调用栈： 递归深度决定了调用栈占用的空间。

举例分析：

// 例子1: O(1) 空间复杂度
int Sum(int a, int b) {int result = a + b; // 只使用一个额外变量 resultreturn result;
}// 例子2: O(n) 空间复杂度
int[] CopyArray(int[] arr) {int[] newArr = new int[arr.Length]; // 创建了一个大小为 N 的新数组for (int i = 0; i < arr.Length; i++) {newArr[i] = arr[i];}return newArr;
}// 例子3: 递归的 O(n) 空间复杂度 (递归栈)
int Fibonacci(int n) {if (n <= 1) return n;return Fibonacci(n - 1) + Fibonacci(n - 2); // 递归深度为 N
}

理解时间复杂度和空间复杂度，是你在算法面试中能够与面试官有效交流、并提出优化方案的基础。很多时候，空间换时间是一种常见的优化策略，比如利用哈希表来将 O(n2) 的查找优化到 O(n) 甚至 O(1)。

数组：最基础也是最重要的基石

数组（Array）是所有编程语言中最基本、最常用的数据结构之一。在 C# 中，你可以声明 int[]、string[] 甚至是 GameObject[]。它是一系列相同类型元素的有序集合，并且通常是在内存中连续存储的。

数组的特性

连续存储： 数组的元素在内存中是紧密排列的。
随机访问： 由于连续存储，可以通过索引 O(1) 时间直接访问任意元素。这是数组最大的优势。
定长（通常）： 在很多语言中（包括 C# 的原生数组），数组一旦创建，其大小就固定了。如果需要改变大小，通常需要创建一个新的数组并复制旧数组的元素。
插入和删除效率低： 由于连续存储的特性，在数组中间插入或删除元素，需要移动后续所有元素，其时间复杂度为 O(N)。

数组的基本操作

创建与初始化：

int[] numbers = new int[5]; // 创建一个包含5个整数的数组，默认值为0
int[] scores = { 90, 85, 92, 78, 95 }; // 创建并初始化

访问元素： 通过索引访问，索引从 0 开始。

int firstScore = scores[0]; // 90
int thirdScore = scores[2]; // 92

遍历数组：

// for 循环
for (int i = 0; i < scores.Length; i++) {Console.WriteLine(scores[i]);
}
// foreach 循环 (适用于只读遍历)
foreach (int score in scores) {Console.WriteLine(score);
}

修改元素：

scores[1] = 88; // 将第二个元素从 85 修改为 88

插入/删除元素（中低效率操作）：

这些操作需要手动实现元素的移动。例如，在索引 i 处插入元素，需要将 i 及之后的所有元素向后移动一位；删除同理。

// 假设在索引为1的位置插入99
// 实际操作会创建一个更大的新数组，然后复制，或者手动移动
// 这里只示意逻辑，实际C#中可使用List<T>
// 对于原生数组，插入删除会比较麻烦，所以面试题通常是要求原地修改或者移除。

经典面试题与解法：数组篇

理解数组的基本特性后，我们来看几个经典的面试题，它们不仅考察你对数组的掌握，更引入了重要的解题技巧。

1. 两数之和 (Two Sum)

题目描述：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

输入: nums = [2, 7, 11, 15], target = 9

输出: [0, 1]

解释: 因为 nums[0] + nums[1] == 9 ，所以返回 [0, 1]。
解题思路 1：暴力枚举 (Brute Force)

最直观的方法是遍历数组中每一个元素 x，然后再次遍历后续元素 y，检查它们是否满足 x + y == target。
- 代码实现：
  
  C#
```
public int[] TwoSumBruteForce(int[] nums, int target) {for (int i = 0; i < nums.Length; i++) {for (int j = i + 1; j < nums.Length; j++) { // j 从 i+1 开始，避免重复使用同一元素if (nums[i] + nums[j] == target) {return new int[] { i, j };}}}// 题目保证有解，所以理论上不会执行到这里throw new ArgumentException("No two sum solution");
}
```
- 复杂度分析：
  - 时间复杂度：O(N2)。外层循环执行 N 次，内层循环执行 N−1,N−2,…,1 次，大约是 NtimesN/2 次操作，所以是 O(N2)。
  - 空间复杂度：O(1)。只使用了常数个额外变量。
解题思路 2：哈希表优化 (Hash Table Optimization) - 空间换时间

暴力解法之所以慢，是因为我们每次都要遍历内部循环来寻找 target - x。如果能更快地找到这个“差值”呢？

我们可以利用哈希表（Dictionary/HashMap）的平均 O(1) 查找效率。

遍历数组，对于每个元素 num：
1. 计算**complement = target - num**。
2. 检查哈希表中是否已经存在 complement。
  - 如果存在，说明我们找到了两个数，直接返回 complement 的索引和当前 num 的索引。
  - 如果不存在，将当前 num 和它的索引存入哈希表，以便后续元素查找。
- 代码实现：
  
  C#
```
using System.Collections.Generic; // 引入 Dictionarypublic int[] TwoSumHashTable(int[] nums, int target) {// key: 数组元素的值, value: 数组元素的索引Dictionary<int, int> map = new Dictionary<int, int>();for (int i = 0; i < nums.Length; i++) {int complement = target - nums[i];// 检查哈希表中是否包含 complementif (map.ContainsKey(complement)) {// 如果包含，说明找到了，返回 complement 的索引和当前元素的索引return new int[] { map[complement], i };}// 如果不包含，将当前元素及其索引加入哈希表map[nums[i]] = i;}throw new ArgumentException("No two sum solution");
}
```
- 复杂度分析：
  - 时间复杂度：O(N)。我们只遍历了一次数组，哈希表的查找和插入操作平均都是 O(1)。
  - 空间复杂度：O(N)。在最坏情况下，哈希表会存储数组中所有的元素。
思考： 这个题目完美地体现了**“空间换时间”**的策略。通过牺牲额外的内存空间（哈希表），我们极大地提升了算法的运行速度。在面试中，当你给出暴力解后，面试官通常会期待你提出这种优化方案。

2. 移除元素 (Remove Element)

题目描述：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

输入: nums = [3, 2, 2, 3], val = 3

输出: 2, nums = [2, 2, _, _] (新长度为 2，原数组的前两个元素是 2)
解题思路：快慢指针 (Two Pointers - Fast and Slow)

“原地修改”且“O(1) 空间”是这道题目的关键提示。快慢指针是解决这类数组原地修改问题的利器。

我们维护两个指针：
- 快指针 (Fast Pointer)：遍历整个数组，寻找不等于 val 的元素。
- 慢指针 (Slow Pointer)：指向当前应该放置不等于 val 的元素的位置。
遍历过程中：
1. 如果快指针指向的元素不等于 val，说明它是一个需要保留的元素。我们将其复制到慢指针指向的位置，然后同时将快指针和慢指针都向前移动一步。
2. 如果快指针指向的元素等于 val，说明它是一个需要移除的元素。我们跳过它，只将快指针向前移动一步。慢指针保持不动，因为它指向的位置还没有被填充。
最终，慢指针所指向的位置就是新数组的长度。
- 代码实现：
  
  C#
```
public int RemoveElement(int[] nums, int val) {int slow = 0; // 慢指针，指向下一个要放置非val元素的位置// fast 从 0 开始遍历整个数组for (int fast = 0; fast < nums.Length; fast++) {if (nums[fast] != val) { // 如果快指针指向的元素不是 valnums[slow] = nums[fast]; // 将其复制到慢指针位置slow++; // 慢指针向前移动}// 如果 nums[fast] == val，则 fast 指针继续前进，slow 指针不动，相当于跳过了 val}return slow; // slow 指针最终的位置就是新数组的长度
}
```
- 复杂度分析：
  - 时间复杂度：O(N)。快指针遍历了整个数组一次。
  - 空间复杂度：O(1)。只使用了两个额外变量（fast 和 slow）。
变种：移除有序数组中的重复项 (Remove Duplicates from Sorted Array)

这道题和 Remove Element 思路几乎完全一样，只是判断条件从 nums[fast] != val 变成了 nums[fast] != nums[slow]（确保只有不重复的元素才被保留）。这进一步强化了快慢指针在“原地”操作中的通用性。

3. 旋转数组 (Rotate Array)

题目描述：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例：

输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

输出: [5, 6, 7, 1, 2, 3, 4]

解释:

向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]

向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]

向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4]
解题思路 1：使用额外数组 (Using Extra Array)

最直接的方式是创建一个新的数组，然后将原数组的元素按照旋转后的顺序填充到新数组中。
- 思路： 元素 nums[i] 旋转 k 次后，它的新位置是 (i + k) % N（其中 N 是数组长度）。
- 代码实现：
  
  C#
```
public void RotateExtraArray(int[] nums, int k) {int n = nums.Length;k %= n; // 确保 k 在 [0, n-1] 范围内int[] newArr = new int[n];for (int i = 0; i < n; i++) {newArr[(i + k) % n] = nums[i]; // 将原位置 i 的元素放到新位置 (i+k)%n}// 将新数组的内容复制回原数组for (int i = 0; i < n; i++) {nums[i] = newArr[i];}
}
```
- 复杂度分析：
  - 时间复杂度：O(N)。两次遍历数组。
  - 空间复杂度：O(N)。创建了一个新的辅助数组。
解题思路 2：三次反转 (Three Reversals) - 原地操作的优雅解法

这是一种非常巧妙且高效的原地旋转方法，其核心思想是：
1. 反转整个数组。
2. 反转前 k 个元素。
3. 反转剩下 N-k 个元素。
我们通过一个例子来理解：nums = [1, 2, 3, 4, 5, 6, 7], k = 3
1. 反转整个数组： [7, 6, 5, 4, 3, 2, 1]
2. 反转前 k 个元素 (即前 3 个)： [5, 6, 7, 4, 3, 2, 1]
3. 反转剩下 N-k 个元素 (即后 4 个)： [5, 6, 7, 1, 2, 3, 4]
得到了正确结果！这种方法的优点是原地操作且高效。
- 辅助函数：反转数组的一部分
  
  C#
```
// 辅助函数：反转数组中从 start 到 end 范围的元素
private void Reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}
```
- 代码实现：
  
  C#
```
public void RotateThreeReversals(int[] nums, int k) {int n = nums.Length;k %= n; // 处理 k > n 的情况// 1. 反转整个数组: [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]Reverse(nums, 0, n - 1);// 2. 反转前 k 个元素: [7,6,5,4,3,2,1] -> [5,6,7,4,3,2,1]Reverse(nums, 0, k - 1);// 3. 反转剩下的 n-k 个元素: [5,6,7,4,3,2,1] -> [5,6,7,1,2,3,4]Reverse(nums, k, n - 1);
}
```
- 复杂度分析：
  - 时间复杂度：O(N)。每次 Reverse 操作都是线性时间，总共执行三次。
  - 空间复杂度：O(1)。完全是原地操作，没有使用额外空间。
思考： 三次反转法是一个非常经典的技巧，它展示了通过巧妙的步骤组合，可以在不使用额外空间的情况下解决复杂问题。在面试中，如果你能给出这种解法，会给面试官留下深刻印象。

4. 合并两个有序数组 (Merge Sorted Array)

题目描述：

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你将 nums2 合并到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n。

示例：

输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

输出：[1, 2, 2, 3, 5, 6]
解题思路：双指针 (从后往前合并)

这道题的难点在于原地合并到 nums1 中，并且 nums1 的后 n 位是空的。如果我们从前往后合并，那么 nums1 中已有的元素可能会被 nums2 中的元素覆盖掉，导致数据丢失。

关键在于从后往前合并。由于 nums1 后半部分有足够的空间，我们可以将 nums1 和 nums2 的最大元素（因为都是有序的）从末尾开始逐一比较，然后将较大的那个放到 nums1 的末尾（也就是合并后数组的末尾）。

我们维护三个指针：
- p1：指向 nums1 中有效部分的末尾（即 m-1）。
- p2：指向 nums2 的末尾（即 n-1）。
- p：指向合并后数组的末尾（即 m+n-1）。
从后往前遍历：
1. 当 p1 和 p2 都还在有效范围内时：
  - 比较 nums1[p1] 和 nums2[p2]。
  - 将较大的元素放到 nums1[p] 的位置。
  - 相应的指针 (p1 或 p2) 和 p 都向前移动一步。
2. 当 p1 已经越界，但 p2 还在有效范围内时：
  - 说明 nums1 的有效元素已经全部处理完毕，但 nums2 中还有剩余元素。
  - 将 nums2 中剩余的元素全部复制到 nums1 的剩余空白位置。
  - p2 和 p 都向前移动一步。
- 代码实现：
  
  C#
```
public void Merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1; // nums1 的有效末尾指针int p2 = n - 1; // nums2 的末尾指针int p = m + n - 1; // 合并后数组的末尾指针// 当 nums2 还有元素未处理时，继续循环while (p2 >= 0) {// 如果 nums1 还有有效元素，并且 nums1[p1] >= nums2[p2]// 注意 p1 >= 0 的条件，避免 nums1 已经处理完而访问越界if (p1 >= 0 && nums1[p1] >= nums2[p2]) {nums1[p] = nums1[p1]; // 将 nums1 中的较大元素放到合并位置p1--; // nums1 指针前移} else {// 否则，nums2[p2] 更大，或者 nums1 已经没有有效元素了nums1[p] = nums2[p2]; // 将 nums2 中的元素放到合并位置p2--; // nums2 指针前移}p--; // 合并位置指针前移}
}
```
- 复杂度分析：
  - 时间复杂度：O(m+n)。指针 p 从 m+n-1 遍历到 0，每个元素至多被检查和移动一次。
  - 空间复杂度：O(1)。完全是原地操作，没有使用额外空间。
思考： 这个题目是双指针技巧的又一个经典应用，尤其强调了从后往前操作的思维，这在涉及到数组原地修改且尾部有足够空间时非常有用。

总结与练习

本篇我们深入探讨了算法的基础——时间复杂度和空间复杂度，理解了如何去分析代码的效率。然后，我们学习了最基础的数据结构——数组，掌握了它的基本特性，并通过两数之和（引入哈希表和空间换时间）、移除元素（引入快慢指针）、旋转数组（引入三次反转法）和合并两个有序数组（引入从后往前双指针）这四个经典面试题，初步接触了面试中常见的解题思路和技巧。

这些技巧都是后续学习的基础，它们的核心思想贯穿在更复杂的数据结构和算法中。请务必理解每种解法的思路，而不仅仅是记住代码。

本篇核心知识点回顾：