算法入門第一篇：算法核心：復雜度分析與數組基礎

引言：為什么需要學習算法？

你可能也發現，即使是社招，面試官也時不時會拋出幾道算法題，從簡單的反轉鏈表到復雜的動態規劃。這常常讓人感到困惑：我一個做游戲開發的，寫好 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)。完全是原地操作，沒有使用額外空間。
思考： 這個題目是雙指針技巧的又一個經典應用，尤其強調了從后往前操作的思維，這在涉及到數組原地修改且尾部有足夠空間時非常有用。

總結與練習

本篇我們深入探討了算法的基礎——時間復雜度和空間復雜度，理解了如何去分析代碼的效率。然后，我們學習了最基礎的數據結構——數組，掌握了它的基本特性，并通過兩數之和（引入哈希表和空間換時間）、移除元素（引入快慢指針）、旋轉數組（引入三次反轉法）和合并兩個有序數組（引入從后往前雙指針）這四個經典面試題，初步接觸了面試中常見的解題思路和技巧。

這些技巧都是后續學習的基礎，它們的核心思想貫穿在更復雜的數據結構和算法中。請務必理解每種解法的思路，而不僅僅是記住代碼。

本篇核心知識點回顧：