經典數組算法題匯總：求和、極值、分治、位運算與雙指針技巧

前言

數組是最基礎的數據結構，也是面試與算法競賽的高頻考點。本文匯總了十餘道經典數組問題，涵蓋遞歸、分治、位運算、雙指針、二分查找、滑動窗口等核心技巧，並提供 C/C++ 風格的參考實現，幫助你建立完整的解題思維框架。

一、基礎遞歸：數組求和

題目：給定含 n 個整數的數組，僅用一行遞歸代碼求和。
思路：邊界條件 n=0 返回 0；否則返回前 n-1 項和加上第 n 項。
代碼：

int sum(int *a, int n) {
    return n == 0 ? 0 : sum(a, n - 1) + a[n - 1];
}

二、分治法：最大值與最小值

題目：求數組最大值與最小值。
思路：將數組二分，遞歸求左右半部的極值，再合併。將比較次數從 2n-2 降至約 1.5n。
代碼：

void MaxMin(int *a, int l, int r, int &maxV, int &minV) {
    if (l == r) { maxV = minV = a[l]; return; }
    if (l + 1 == r) {
        if (a[l] >= a[r]) { maxV = a[l]; minV = a[r]; }
        else { maxV = a[r]; minV = a[l]; }
        return;
    }
    int m = (l + r) / 2;
    int lmax, lmin, rmax, rmin;
    MaxMin(a, l, m, lmax, lmin);
    MaxMin(a, m+1, r, rmax, rmin);
    maxV = max(lmax, rmax);
    minV = min(lmin, rmin);
}

三、分治法：最大值與次大值

題目：求最大值與第二大值。
思路：同分治，合併時比較左右兩組的最大值，較大者為整體最大值，另一組的最大值與較小組的最大值比較得出次大值。
代碼關鍵合併邏輯：

max = leftmax > rightmax ? leftmax : rightmax;
second = leftmax < rightmax ? leftmax : rightmax; // 此處需嚴謹處理邊界

四、摩爾投票法：出現次數超過半數的元素

題目：數組中某元素出現 > n/2 次，找出該元素。
思路：維護候選值與計數器，相同則+1，不同則-1，歸零時換候選。最終候選即為答案。
代碼：

int FindMajority(int* a, int n) {
    int cand = a[0], cnt = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] == cand) ++cnt;
        else if (--cnt < 0) { cand = a[i]; cnt = 1; }
    }
    return cand; // 題目保證存在，無需二次驗證
}

備選：排序後取中位數 a[n/2]，時間 O(n log n)。

五、排序後遍歷：最短距離數對

題目：找出兩元素差值絕對值最小的數對。
思路：排序後，最小差值必出現在相鄰元素間。單次遍歷即可。
代碼：

void MinDistance(int* a, int n) {
    qsort(a, n, sizeof(int), cmp);
    int minD = INT_MAX, x, y;
    for (int i = 0; i < n-1; ++i) {
        if (a[i+1] - a[i] < minD) {
            minD = a[i+1] - a[i];
            x = a[i]; y = a[i+1];
        }
    }
}

六、雙指針：有序數組公共元素 / 兩數之和

1. 公共元素：兩指針 i,j 分別指向兩有序數組頭部，小者前進，相等則輸出並雙進。O(n)。
2. 固定和數對：一指針指頭，一指尾，根據和與目標值大小移動指針。O(n)。

七、三指針 / 二分查找：三個數組的公共元素

• 三數組有序：三指針同步移動，最小者前進，直到三值相等。O(n)。
• 無序：排序兩數組 O(n log n)，遍歷第三數組在前兩者中二分查找 O(n log n)。

八、位運算技巧

• 唯一重複元素 (1~1000 中一個重複)：總和減去 1+...+1000 = 500500。
• 出現奇數次的元素：所有元素異或 (XOR)，偶數次抵消為 0，剩下奇數次者。int r = 0; for (int x : a) r ^= x;

九、動態規劃 / 貪心：最大子段和與積

最大子段和 (Kadane 算法)：維護以當前元素結尾的最大和 cur 及全局最大和 ans。cur = max(0, cur + a[i]); ans = max(ans, cur);
最大子段積：需同時維護當前最大正積與最小負積，遇負數交換兩者。見文中完整代碼。

十、原地逆序與循環移位

• 數組右循環移位 k 位：三次逆序法。逆序前 n-k、後 k、再整體逆序。O(n)、O(1) 空間。
• 字符串原地逆序：雙指針首尾交換，向中間收攏。

十一、回溯法：組合生成

從 n 中選 m，經典 DFS 回溯，利用 buffer 記錄當前路徑，IsValid 保證遞增順序避免重複。

十二、歸併與原地整理

• 合併兩有序數組去重：雙指針歸併，相等時只取一個。O(n)。
• 非零元素相對順序不變移零到尾：從後向前掃描，維護零元素位置 k，遇非零與 a[k] 交換。O(n)、O(1)。

總結

數組題核心模式有限：有序→二分/雙指針；無序→排序+二分/哈希/位運算。熟練掌握分治、雙指針、位運算、動態規劃、回溯等範式，配合邊界條件處理，即可迎刃而解絕大多數數組問題。