LeetCode 69 大整數乘法：模擬手算與 FFT 優化思路

題目描述

給定兩個以字符串形式表示的非負整數，返回它們的乘積，結果也以字符串形式返回。數字長度任意，不能直接使用內置大整數類型。

解法一：模擬豎式乘法（基礎法）

核心思想：模擬小學手算乘法過程。對於長度分別為 m 和 n 的兩個數，乘積最多 m + n 位。

關鍵步驟

1. 位對位相乘累加：num1[i] * num2[j] 的結果加到 tmp[k - i - j]，其中 k = m + n - 2。
2. 統一進位處理：從低位到高位遍歷 tmp 陣列處理進位。
3. 去除前導零：從最高位向下找第一個非零位；若全為零則返回 "0"。
4. 構建結果字符串：從高位到低位拼接字符。

AC 代碼

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size(), len2 = num2.size();
        vector<int> tmp(len1 + len2, 0);
        int k = len1 + len2 - 2;  // 最低位索引

        // 位對位相乘累加（無進位）
        for (int i = 0; i < len1; ++i) {
            for (int j = 0; j < len2; ++j) {
                tmp[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        // 統一處理進位
        int carry = 0;
        for (int i = 0; i < len1 + len2; ++i) {
            tmp[i] += carry;
            carry = tmp[i] / 10;
            tmp[i] %= 10;
        }

        // 去除前導零
        int i = k + 1;
        while (i >= 0 && tmp[i] == 0) --i;
        if (i < 0) return "0";  // 乘積為 0

        // 構建結果字符串
        string ret;
        for (; i >= 0; --i) ret.push_back(tmp[i] + '0');
        return ret;
    }
};

複雜度分析

• 時間複雜度：O(m × n)
• 空間複雜度：O(m + n)

解法二：快速傅里葉變換（FFT）優化

理論基礎：大整數乘法可視為多項式乘法。設 a = Σ a_i × 10^i，b = Σ b_j × 10^j，則乘積係數 c_k = Σ a_i × b_j (i+j=k)，即向量卷積。

根據卷積定理：向量卷積的離散傅里葉變換 = 向量 DFT 的乘積。利用 FFT 可在 O(N log N) 完成 DFT，其中 N 為結果位數的下一個 2 的冪次。

FFT 計算步驟

1. 對係數向量 {a_i}、{b_j} 分別做 DFT 得到 {A_i}、{B_j}
2. 逐項相乘得到 {C_k = A_k × B_k}
3. 對 {C_k} 做逆 DFT 得到卷積結果 {c_k}
4. 對 {c_k} 進行進位處理得到最終乘積

FFT 關鍵點

• 遞歸分解：長度 N 的 DFT 分解為兩個長度 N/2 的 DFT（奇偶項分離）
• 基例：長度 1 的 DFT 為恆等變換
• 若 N 非 2 的冪次，補零至下一個 2 的冪次
• 時間復雜度：O(N log N)，顯著優於 O(N²)

面試提示：FFT 實現較複雜，面試中通常只需闡述思路與原理，不要求現場編寫完整代碼。參考資料：《使用快速傅里葉變換計算大整數乘法》。