c 字符串数组_LeetCode415字符串加法

这是第68篇LeetCode题解大数加法

昨天的题目大数乘法中涉及到了大数加法，但是那个大数加法写的实在不够优雅，而且效率不够高，因此今天专门做一道大数加法的题目。

1 题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。注意：

num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式。

2 题解

按照加法规则，需要将两个整数按照个位对齐，从右往左进行计算。在对字符数组进行加法的时候也是一样的，因此首先要将两个字符串以各位为基准对齐，这里有两种基本的方法：

将两个字符串逆序之后再相加，相加得到的字符串再逆序即可(这是常规的链表加法的解法)
找到较短的字符串，在较短字符串前面补0使得两个字符串的长度相同之后进行计算

这里使用第1种思路，我使用空间换时间的方式，定义3个整数数组分别保存被加数、jia数和最终的和，数组a和b保存逆序之后的结果，再将加法的结果保存在整数数组c中，最终的代码如下：

class Solution {
public:
    string addStrings(string num1, string num2) {
        vector<int> a(5105, 0), b(5105, 0), c(5105, 0);
        int la = num1.length();
        int lb = num2.length();
        int lc = max(la, lb);
        for (int i = 0; i 1] = num1[i] - '0';
        for (int i = 0; i 1] = num2[i] - '0';
        for (int i = 0; i             c[i] += a[i] + b[i];
            c[i + 1] = c[i] / 10;
            c[i] %= 10;
        }
        string ret;
        if (c[lc] > 0) lc += 1;
        for (int i = lc - 1; i >= 0; i--) ret.append(to_string(c[i]));
        return ret;
    }
};