一、算法概述1.1 问题背景编程语言中的基础数值类型int、long long 等存在固定的取值上限当参与运算的整数位数远超类型承载范围时会发生数值溢出导致计算结果错误。大数运算算法通过字符串、数组或链表来存储超长整数模拟人工竖式计算的逻辑实现任意精度的加减乘运算。1.2 核心思想模拟纸笔竖式计算的规则从低位到高位逐位处理数值统一管理进位 / 借位最终拼接得到完整的运算结果。所有大数运算的底层逻辑都对齐人工计算习惯核心难点在于边界处理与进位控制。1.3 常见考察题型字符串形式大数加法字符串形式大数乘法链表形式大数加法高位在前 / 低位在前大数减法拓展题型二、字符串大数加法2.1 题目描述输入两个以字符串形式表示的非负整数返回它们的和同样以字符串形式输出。数字长度可达数千位无法用普通整型存储。2.2 核心思路低位对齐从两个字符串的末尾个位开始同步向左遍历。逐位求和每一位的和 第一个数当前位 第二个数当前位 上一位的进位当前位结果为sum % 10新进位为sum / 10。循环终止两个字符串均遍历完毕且进位为 0 时停止。结果反转由于从低位开始拼接结果最终需要反转字符串得到正确的高位到低位顺序。2.3 标准实现反转法通过反转字符串将低位统一到下标 0 位置简化循环逻辑避免双指针下标管理。cpp运行string addStrings(string num1, string num2) { reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); string res; int carry 0; int i 0; while (i num1.size() || i num2.size() || carry) { int sum carry; if (i num1.size()) sum num1[i] - 0; if (i num2.size()) sum num2[i] - 0; carry sum / 10; res.push_back(sum % 10 0); i; } reverse(res.begin(), res.end()); return res; }2.4 复杂度分析时间复杂度O(max(n, m))n、m 为两个输入数字的长度空间复杂度O (1)不计入结果存储的额外空间2.5 易错点遗漏最终进位例如999 1数字遍历完成后仍有进位 1必须加入结果。字符与数字转换错误忘记执行- 0或 0操作。长度不一致处理短字符串遍历完毕后后续位按 0 处理不可直接终止循环。三、字符串大数乘法3.1 题目描述输入两个字符串形式的非负整数返回它们的乘积以字符串形式输出。3.2 核心原理位置映射长度为 n 的数字与长度为 m 的数字相乘乘积的最大长度为n m。 对于num1[i]和num2[j]均从左到右下标高位到低位乘积的低位结果落在结果数组的i j 1位置乘积的高位进位落在结果数组的i j位置3.3 实现步骤边界特判任意一个输入为0直接返回0。初始化大小为 nm 的整型数组初始值全为 0。逆序双重遍历两个字符串计算每位乘积累加到数组对应位置并实时处理进位。跳过结果数组的前导零将数组转换为字符串输出。3.4 标准实现代码cpp运行string multiply(string num1, string num2) { if (num1 0 || num2 0) return 0; int n num1.size(), m num2.size(); vectorint res(n m, 0); for (int i n - 1; i 0; --i) { int a num1[i] - 0; for (int j m - 1; j 0; --j) { int b num2[j] - 0; int mul a * b; int p1 i j, p2 i j 1; int sum mul res[p2]; res[p2] sum % 10; res[p1] sum / 10; } } string ans; for (int num : res) { if (!(ans.empty() num 0)) { ans.push_back(num 0); } } return ans; }3.5 复杂度分析时间复杂度O(n × m)双重循环遍历每一位数字空间复杂度O (n m)用于存储结果数组3.6 易错点位置映射混淆容易记反ij与ij1的含义建议通过个位、十位的简单案例画图验证。覆盖原有值直接赋值覆盖该位置已有的进位数值导致累加错误。前导零遗漏结果数组头部必然存在若干个 0转换字符串时必须跳过。零值特判缺失输入包含 0 时会返回空串或异常结果。四、链表大数相加高位在前4.1 题目描述两个链表分别表示一个非负整数链表头节点为数字最高位返回相加后的链表同样保持高位在前。 示例9-3-76-31-0-0-04.2 解法一反转链表法空间最优思路反转两个输入链表将 “高位在前” 转换为 “低位在前”适配加法运算顺序。按照大数加法逻辑逐位相加生成低位在前的结果链表。再次反转结果链表恢复高位在前的输出顺序。代码实现cpp运行struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } return pre; } ListNode* addInList(ListNode* head1, ListNode* head2) { ListNode* l1 reverseList(head1); ListNode* l2 reverseList(head2); ListNode dummy(0); ListNode* cur dummy; int carry 0; while (l1 || l2 || carry) { int sum carry; if (l1) { sum l1-val; l1 l1-next; } if (l2) { sum l2-val; l2 l2-next; } carry sum / 10; cur-next new ListNode(sum % 10); cur cur-next; } return reverseList(dummy.next); }4.3 解法二栈辅助法逻辑直观思路利用栈 “后进先出” 的特性将链表节点依次压入栈中弹出时自然从低位开始计算使用头插法构建结果链表保证最终链表高位在前。核心代码cpp运行ListNode* addInList(ListNode* head1, ListNode* head2) { stackint st1, st2; while (head1) { st1.push(head1-val); head1 head1-next; } while (head2) { st2.push(head2-val); head2 head2-next; } ListNode* res nullptr; int carry 0; while (!st1.empty() || !st2.empty() || carry) { int sum carry; if (!st1.empty()) { sum st1.top(); st1.pop(); } if (!st2.empty()) { sum st2.top(); st2.pop(); } carry sum / 10; // 头插法构建结果 ListNode* node new ListNode(sum % 10); node-next res; res node; } return res; }4.4 方案对比表格方案空间复杂度优势劣势反转链表法O (1)不计结果空间最优面试加分项需手写反转函数指针操作易出错栈辅助法O(nm)逻辑直观代码简洁额外占用栈空间五、通用避坑与面试经验5.1 边界条件必查清单进位收尾所有大数加法类题目循环条件必须包含carry ! 0防止最高位进位丢失。零值特判乘法题目必须先判断输入是否为 0避免返回空字符串或异常结果。长度差异两个数字 / 链表长度不一致时短的一方遍历完毕后按 0 处理不可提前终止循环。前导零清理乘法结果必须跳过数组开头的 0加法通常无此问题但输入含前导零时需按题意处理。5.2 代码书写技巧统一低位优先字符串反转、链表反转、栈压栈本质都是将 “高位在前” 的存储格式转换为 “低位在前” 的运算格式统一逻辑。哑节点技巧链表题目使用哑节点Dummy Node可以避免头节点特殊判断大幅简化代码。字符转换检查c - 0转为整型数字x 0转回字符写完后立刻核对避免低级错误。5.3 面试答题策略先点明数值溢出的问题背景再引出 “模拟竖式运算” 的核心思路。加法优先讲解反转法乘法重点阐述ij位置映射的规律。链表题先给出反转法空间最优方案再补充栈解法作为备选。主动提及边界测试用例全 9 加 1、其中一个数为 0、两数长度相差悬殊。六、进阶拓展方向大数减法思路与加法类似需先比较两数大小确定符号逐位相减并处理借位。FFT 快速乘法基于快速傅里叶变换将时间复杂度优化至 O ((nm) log (nm))适用于超长大数运算竞赛场景常用面试一般不要求手写。大数除法通常结合减法实现模拟长除法的运算逻辑。谢谢