题解 | #大数加法#

题目主要信息:

• 以字符串形式读入两个正整数，返回其相加结果
• 结果也是字符串形式
• 字符串只有数字0-9

具体思路:

大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加。

• step 1：若是其中一个字符串为空，直接返回另一个，不用加了。
• step 2：交换两个字符串的位置，我们是s为较长的字符串，t为较短的字符串，结果也记录在较长的字符串中。
• step 3：从后往前遍历字符串s，每次取出字符转数字，加上进位制，将下标转换为字符串t中从后往前相应的下标，如果下标为非负数则还需要加上字符串t中相应字符转化的数字。
• step 4：整型除法取进位，取模算法去掉十位，将计算后的结果放入较长数组对应位置。
• step 5：如果遍历结束，进位值还有，则需要直接在字符串s前增加一个字符‘1’。

具体过程可以参考如下图示：

代码实现:

class Solution {
public:
    string solve(string s, string t) {
        //若是其中一个为空，返回另一个
        if(s.empty())
            return t;
        if(t.empty())
            return s;
        if(s.length() < t.length()) //让s为较长的，t为较短的
            swap(s, t);
        int carry = 0; //进位标志
        for(int i = s.length() - 1; i >= 0; i--){ //从后往前遍历较长的字符串
            int temp = s[i] - '0' + carry; //转数字加上进位
            int j = i - s.length() + t.length(); //转较短的字符串相应的从后往前的下标
            if(j >= 0) //如果较短字符串还有
                temp += t[j] - '0'; //转数组相加
            carry = temp / 10; //取进位
            temp = temp % 10; //去十位
            s[i] = temp + '0'; //修改结果
        }
        if(carry == 1) //最后的进位
            s = '1' + s;
        return s;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为较长字符的长度，遍历字符串
• 空间复杂度：$O(1)O(1)$，常数级空间，没有使用额外辅助空间