1. 问题背景与需求分析今天我们要讨论的是LeetCode第989题数组形式的整数加法。这是一道看似简单却暗藏玄机的经典题目我在实际解题过程中发现不少初学者容易陷入性能陷阱。题目要求我们将一个用数组表示的整数例如A [1,2,0,0]表示数字1200与一个普通整数K相加返回数组形式的和。这个问题的核心难点在于大数处理当K值很大比如1e9时直接转换为数组可能导致溢出进位处理特别是最高位产生进位时需要数组扩容性能优化如何在O(n)时间复杂度内完成操作我最初提交的解法运行时间为120ms经过多次优化后最终实现了100ms的耗时成绩击败了98%的C提交。下面分享我的完整解题思路和优化历程。2. 基础解法与性能瓶颈2.1 直观解法分析最直接的思路是将数组转换为数字与K相加后再转换回数组vectorint addToArrayForm(vectorint A, int K) { long num 0; for(int n : A) num num * 10 n; num K; vectorint res; if(num 0) return {0}; while(num 0) { res.insert(res.begin(), num % 10); num / 10; } return res; }这个解法存在三个严重问题整数溢出当数组表示的数字超过LONG_MAX时会出错时间复杂度insert操作是O(n)复杂度整体变为O(n²)空间浪费频繁在头部插入导致多次内存重分配2.2 性能测试数据我在LeetCode测试平台上对比了不同解法的表现解法类型时间复杂度空间复杂度实际耗时(ms)转换法O(n²)O(n)120逐位相加O(n)O(n)108优化进位O(n)O(1)1003. 优化解法实现3.1 逐位相加法正确的做法是模拟手工加法过程vectorint addToArrayForm(vectorint A, int K) { vectorint res; int carry K; int i A.size() - 1; while(i 0 || carry 0) { if(i 0) carry A[i--]; res.push_back(carry % 10); carry / 10; } reverse(res.begin(), res.end()); return res; }这个解法有几点关键优化从最低位开始处理避免数组头部插入将K作为初始进位值统一处理逻辑最后一次性反转数组时间复杂度降为O(n)3.2 原地修改优化如果允许修改输入数组可以进一步优化空间vectorint addToArrayForm(vectorint A, int K) { for(int i A.size() - 1; i 0 K 0; --i) { K A[i]; A[i] K % 10; K / 10; } while(K 0) { A.insert(A.begin(), K % 10); K / 10; } return A; }这种写法的优势在于大部分情况下不需要额外空间只有最高位进位时才需要扩容减少了vector的构造和拷贝开销4. 边界条件与测试用例4.1 必须考虑的边界情况空数组输入虽然题目保证非空但实际工程中需要处理K为0的情况需要特殊处理吗最高位进位如[9,9]1[1,0,0]前导零题目保证输入无前导零但输出可能有4.2 关键测试用例TEST_CASE(Add to Array Form) { vectorint case1 {1,2,0,0}; REQUIRE(addToArrayForm(case1, 34) vectorint{1,2,3,4}); vectorint case2 {9,9,9}; REQUIRE(addToArrayForm(case2, 1) vectorint{1,0,0,0}); vectorint case3 {0}; REQUIRE(addToArrayForm(case3, 0) vectorint{0}); vectorint case4 {2,1,5}; REQUIRE(addToArrayForm(case4, 806) vectorint{1,0,2,1}); }5. 性能优化技巧5.1 预分配空间提前计算可能的最大位数避免多次扩容int maxLen max(A.size(), to_string(K).length()) 1; res.reserve(maxLen);5.2 使用emplace_back减少临时对象构造res.emplace_back(carry % 10);5.3 避免不必要的反转可以改用deque或直接反向填充vectorint res; int i A.size() - 1; while(i 0 || K 0) { if(i 0) K A[i--]; res.push_back(K % 10); K / 10; } return vectorint(res.rbegin(), res.rend());6. 不同语言实现对比6.1 Java实现特点Java需要注意ArrayList和LinkedList的选择public ListInteger addToArrayForm(int[] A, int K) { LinkedListInteger res new LinkedList(); int i A.length - 1; while(i 0 || K 0) { if(i 0) K A[i--]; res.addFirst(K % 10); K / 10; } return res; }6.2 Python实现的技巧Python可以利用divmod简化代码def addToArrayForm(A, K): res [] for i in range(len(A)-1, -1, -1): K A[i] res.append(K % 10) K // 10 while K 0: res.append(K % 10) K // 10 return res[::-1]7. 常见错误与调试技巧7.1 典型错误模式忘记处理最高位进位// 错误示例 while(i 0) { // 可能漏掉K还有值的情况 // ... }进位计算错误carry (A[i] K % 10) / 10; // 错误的分步计算前导零问题if(res.empty()) return {0}; // 多余的检查7.2 调试建议打印中间变量cout i i K K digit K%10 endl;使用边界值测试// 测试最大输入 vectorint largeA(10000, 9); int largeK INT_MAX; auto result addToArrayForm(largeA, largeK);性能分析工具g -pg main.cpp ./a.out gprof a.out gmon.out analysis.txt8. 算法扩展思考8.1 大数运算通用模式这个问题的解法可以推广到大数加法vectorint addTwoNumbers(vectorint a, vectorint b) { vectorint res; int carry 0; int i a.size()-1, j b.size()-1; while(i 0 || j 0 || carry) { if(i 0) carry a[i--]; if(j 0) carry b[j--]; res.push_back(carry % 10); carry / 10; } reverse(res.begin(), res.end()); return res; }8.2 其他表示形式的转换类似问题还有链表表示的数字相加LeetCode 2字符串表示的大数相乘LeetCode 43科学计数法转换8.3 实际工程应用这种技巧在以下场景很有用金融系统中的精确计算密码学中的大数运算高精度科学计算我在实际项目中处理过银行交易系统的金额计算就采用了类似的数组表示法来避免浮点数精度问题。一个经验是当处理超过15位有效数字时一定要使用数组或字符串表示法。 
长河君 · 2026/10/26 6:47:11 · 阅读 1.2k LeetCode 989题：数组形式整数加法的优化解法
1. 问题背景与需求分析今天我们要讨论的是LeetCode第989题数组形式的整数加法。这是一道看似简单却暗藏玄机的经典题目我在实际解题过程中发现不少初学者容易陷入性能陷阱。题目要求我们将一个用数组表示的整数例如A [1,2,0,0]表示数字1200与一个普通整数K相加返回数组形式的和。这个问题的核心难点在于大数处理当K值很大比如1e9时直接转换为数组可能导致溢出进位处理特别是最高位产生进位时需要数组扩容性能优化如何在O(n)时间复杂度内完成操作我最初提交的解法运行时间为120ms经过多次优化后最终实现了100ms的耗时成绩击败了98%的C提交。下面分享我的完整解题思路和优化历程。2. 基础解法与性能瓶颈2.1 直观解法分析最直接的思路是将数组转换为数字与K相加后再转换回数组vectorint addToArrayForm(vectorint A, int K) { long num 0; for(int n : A) num num * 10 n; num K; vectorint res; if(num 0) return {0}; while(num 0) { res.insert(res.begin(), num % 10); num / 10; } return res; }这个解法存在三个严重问题整数溢出当数组表示的数字超过LONG_MAX时会出错时间复杂度insert操作是O(n)复杂度整体变为O(n²)空间浪费频繁在头部插入导致多次内存重分配2.2 性能测试数据我在LeetCode测试平台上对比了不同解法的表现解法类型时间复杂度空间复杂度实际耗时(ms)转换法O(n²)O(n)120逐位相加O(n)O(n)108优化进位O(n)O(1)1003. 优化解法实现3.1 逐位相加法正确的做法是模拟手工加法过程vectorint addToArrayForm(vectorint A, int K) { vectorint res; int carry K; int i A.size() - 1; while(i 0 || carry 0) { if(i 0) carry A[i--]; res.push_back(carry % 10); carry / 10; } reverse(res.begin(), res.end()); return res; }这个解法有几点关键优化从最低位开始处理避免数组头部插入将K作为初始进位值统一处理逻辑最后一次性反转数组时间复杂度降为O(n)3.2 原地修改优化如果允许修改输入数组可以进一步优化空间vectorint addToArrayForm(vectorint A, int K) { for(int i A.size() - 1; i 0 K 0; --i) { K A[i]; A[i] K % 10; K / 10; } while(K 0) { A.insert(A.begin(), K % 10); K / 10; } return A; }这种写法的优势在于大部分情况下不需要额外空间只有最高位进位时才需要扩容减少了vector的构造和拷贝开销4. 边界条件与测试用例4.1 必须考虑的边界情况空数组输入虽然题目保证非空但实际工程中需要处理K为0的情况需要特殊处理吗最高位进位如[9,9]1[1,0,0]前导零题目保证输入无前导零但输出可能有4.2 关键测试用例TEST_CASE(Add to Array Form) { vectorint case1 {1,2,0,0}; REQUIRE(addToArrayForm(case1, 34) vectorint{1,2,3,4}); vectorint case2 {9,9,9}; REQUIRE(addToArrayForm(case2, 1) vectorint{1,0,0,0}); vectorint case3 {0}; REQUIRE(addToArrayForm(case3, 0) vectorint{0}); vectorint case4 {2,1,5}; REQUIRE(addToArrayForm(case4, 806) vectorint{1,0,2,1}); }5. 性能优化技巧5.1 预分配空间提前计算可能的最大位数避免多次扩容int maxLen max(A.size(), to_string(K).length()) 1; res.reserve(maxLen);5.2 使用emplace_back减少临时对象构造res.emplace_back(carry % 10);5.3 避免不必要的反转可以改用deque或直接反向填充vectorint res; int i A.size() - 1; while(i 0 || K 0) { if(i 0) K A[i--]; res.push_back(K % 10); K / 10; } return vectorint(res.rbegin(), res.rend());6. 不同语言实现对比6.1 Java实现特点Java需要注意ArrayList和LinkedList的选择public ListInteger addToArrayForm(int[] A, int K) { LinkedListInteger res new LinkedList(); int i A.length - 1; while(i 0 || K 0) { if(i 0) K A[i--]; res.addFirst(K % 10); K / 10; } return res; }6.2 Python实现的技巧Python可以利用divmod简化代码def addToArrayForm(A, K): res [] for i in range(len(A)-1, -1, -1): K A[i] res.append(K % 10) K // 10 while K 0: res.append(K % 10) K // 10 return res[::-1]7. 常见错误与调试技巧7.1 典型错误模式忘记处理最高位进位// 错误示例 while(i 0) { // 可能漏掉K还有值的情况 // ... }进位计算错误carry (A[i] K % 10) / 10; // 错误的分步计算前导零问题if(res.empty()) return {0}; // 多余的检查7.2 调试建议打印中间变量cout i i K K digit K%10 endl;使用边界值测试// 测试最大输入 vectorint largeA(10000, 9); int largeK INT_MAX; auto result addToArrayForm(largeA, largeK);性能分析工具g -pg main.cpp ./a.out gprof a.out gmon.out analysis.txt8. 算法扩展思考8.1 大数运算通用模式这个问题的解法可以推广到大数加法vectorint addTwoNumbers(vectorint a, vectorint b) { vectorint res; int carry 0; int i a.size()-1, j b.size()-1; while(i 0 || j 0 || carry) { if(i 0) carry a[i--]; if(j 0) carry b[j--]; res.push_back(carry % 10); carry / 10; } reverse(res.begin(), res.end()); return res; }8.2 其他表示形式的转换类似问题还有链表表示的数字相加LeetCode 2字符串表示的大数相乘LeetCode 43科学计数法转换8.3 实际工程应用这种技巧在以下场景很有用金融系统中的精确计算密码学中的大数运算高精度科学计算我在实际项目中处理过银行交易系统的金额计算就采用了类似的数组表示法来避免浮点数精度问题。一个经验是当处理超过15位有效数字时一定要使用数组或字符串表示法。