題目描述

給定兩個非負整數字符串 num1、num2，返回它們乘積的字符串形式。不能使用內置大整數庫或直接轉換為整數。

核心算法：豎式乘法模擬

num1[i] * num2[j] 的結果位於乘積的第 i+j 位（從右向左 0-based）。利用數組 res[i+j] 累加乘積，最後統一處理進位。

步驟詳解

1. 反轉兩字符串，便於索引對應位權
2. 雙層循環計算 digit1 * digit2，累加到 res[i+j]
3. 遍歷 res 處理進位：res[k+1] += res[k] / 10; res[k] %= 10;
4. 反轉 res，跳過前導零，轉為字符串

代碼實現

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        int n = num1.size(), m = num2.size();
        vector res(n + m, 0); // 最大長度 n+m

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < n; i++) {
            int d1 = num1[i] - '0';
            for (int j = 0; j < m; j++) {
                int d2 = num2[j] - '0';
                res[i + j] += d1 * d2; // 累加到對應位
            }
        }

        // 統一處理進位
        for (int k = 0; k < n + m - 1; k++) {
            res[k + 1] += res[k] / 10;
            res[k] %= 10;
        }

        // 跳過前導零，構建結果字符串
        int idx = n + m - 1;
        while (idx > 0 && res[idx] == 0) idx--;
        string ans;
        for (; idx >= 0; idx--) ans.push_back('0' + res[idx]);
        return ans;
    }
};

複雜度分析

• 時間：O(n×m) —— 雙層循環
• 空間：O(n+m) —— 結果數組

優化方向：FFT 加速

利用快速傅里葉變換將多項式乘法（數字乘法本質）優化至 O((n+m) log(n+m))。步驟：

1. 將數字視為係數多項式
2. FFT 變換至點值表示
3. 點值相乘
4. IFFT 變換回係數表示
5. 處理進位得結果

競賽中常用 NTT（數論變換，模素數避免精度誤差）。LeetCode 此題 O(n²) 通過，FFT 屬進階拓展。

關鍵細節

• 結果最大長度 len1 + len2（如 99×99=9801，4 位 = 2+2）
• 進位處理順序：從低位向高位
• 前導零處理：保留至少一位（結果為 0 時）