描述

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：s.length,t.length<=100000，字符串仅由'0'~'9'构成

要求：时间复杂度 O(n)

思路1：模拟加法

从低位开始相加，计算进位

public class Solution {
    public String solve (String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        StringBuilder sb = new StringBuilder();
        int flag = 0;
        while(i >= 0 || j >= 0) {
            int val = flag;
            if(i >= 0) {
                val += s.charAt(i) - '0';
                i--;
            }
            if(j >= 0) {
                val += t.charAt(j) - '0';
                j--;
            }
            // 进位
            flag = val / 10;
            // insert插入到头部
            sb.insert(0, val % 10);
        }
        if(flag == 1) {
            sb.insert(0, 1);
        }
        return sb.toString();
    }
}

使用StringBuilder.insert插入头部，需要不断移动数组，效率较低。

可以使用栈暂存（空间和时间都比较大）

public class Solution {
    public String solve (String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int flag = 0;
        Stack<Integer> stack = new Stack<>();
        while(i >= 0 || j >= 0) {
            int val = flag;
            if(i >= 0) {
                val += s.charAt(i) - '0';
                i--;
            }
            if(j >= 0) {
                val += t.charAt(j) - '0';
                j--;
            }
            flag = val / 10;
            // 使用栈存储
            stack.push(val % 10);
        }
        StringBuilder sb = new StringBuilder();
        if(flag == 1) {
            sb.append(1);
        }
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}

也可以先append，再反转字符串（目前看来效率最高）

public class Solution {
    public String solve (String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        StringBuilder sb = new StringBuilder();
        int flag = 0;
        while(i >= 0 || j >= 0) {
            int val = flag;
            if(i >= 0) {
                val += s.charAt(i) - '0';
                i--;
            }
            if(j >= 0) {
                val += t.charAt(j) - '0';
                j--;
            }
            flag = val / 10;
            // append追加到尾部
            sb.append(val % 10);
        }
        if(flag == 1) {
            sb.append(1);
        }
        // 反转字符串
        return sb.reverse().toString();
    }
}

思路2：BigInteger

部分语言目前支持大数相加，可以直接使用。（不推荐使用，不是考察重点，且耗时和空间都比较大）

//导入math包
import java.math.BigInteger;
public class Solution {
    public String solve (String s, String t) {
        BigInteger num1 = new BigInteger(s);
        BigInteger num2 = new BigInteger(t);
        return num1.add(num2).toString();
    }
}