时间复杂度O（n）

C++ 代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> res;
int check(string &a, string &b)
{
    if(a.size() != b.size())
        return a.size() - b.size();
    for(int i = 0; i < a.size(); i++)
        if(a[i] != b[i])
            return a[i] - b[i];
    return 1;
}

void sub(string &a, string &b)
{
    for(int i = a.size()-1, j = b.size()-1, t = 0; i >= 0; i--,j--)
    {
        if(i >= 0) t = a[i] - '0' - t;
        if(j >= 0) t = t - b[j] + '0';
        res.push_back((t + 10)%10);
        if(t >= 0) t = 0;
        else t = 1;
    }
    // 去除前导0,但是最后一个0不能去掉
    while(res.back() == 0 && res.size() > 1)
        res.pop_back();
}

int main()
{
    string a,b;
    std::ios::sync_with_stdio(false);
    cin >> a >> b;
    if(check(a,b) >= 0) sub(a,b);
    else
    {
    sub(b, a);
    cout << "-";
    }
    for(int i = res.size()-1; i >= 0; i--)
        cout << res[i];
    return 0;
}