解题思路

高精度减法：两个不超过 240 位的数相减，数字太大不能直接用 int，要一位一位处理。

思路：

1. 判断正负：如果被减数小于减数，结果会是负数。先比较两个数的长度和大小，小的是被减数就交换，并标记负号
2. 逆序存数组：把数字串逆序存进数组，个位放 a[0]，方便从低位算起
3. 借位相减：从个位开始，如果这一位不够减，就向高位借 1（借来的 1 在这一位算 10）
4. 逐位相减得到结果数组
5. 去掉前导 0：从高位找第一个非 0 的位置，从这里开始输出

为什么逆序存？ 因为减法要从个位（低位）开始算，逆序存放后个位在下标 0，直接从下标 0 开始遍历就是低位到高位，方便借位。

怎么判断谁大谁小？ 先比位数，位数多的大；位数相同再比字典序（从高到低逐位比较）。

举个例子：333...333 - 222...222 = 111...111

• 个位 3-2=1，十位 3-2=1……每一位都够减
• 结果每一位都是 1

参考代码

#include <iostream>
#include <string>
using namespace std;

string s1, s2;
int a[250], b[250], c[250];
int len, p;
char f = '+';

int main() {
    cin >> s1 >> s2;

    if (s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) {
        f = '-';
        swap(s1, s2);
    }

    for (int i = 0; i < s1.size(); i++) a[s1.size() - 1 - i] = s1[i] - '0';
    for (int i = 0; i < s2.size(); i++) b[s2.size() - 1 - i] = s2[i] - '0';

    len = s1.size();

    for (int i = 0; i < len; i++) {  // 借位
        if (a[i] < b[i]) {
            a[i + 1] = a[i + 1] - 1;
            a[i] = a[i] + 10;
        }
    }
    for (int i = 0; i < len; i++) c[i] = a[i] - b[i];  // 相减

    if (f == '-') cout << f;  // 输出负号

    for (int i = len - 1; i >= 0; i--) {  // 找最高位
        if (c[i] != 0) { p = i; break; }
    }
    for (int i = p; i >= 0; i--) cout << c[i];  // 输出
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，N 为位数
• 空间复杂度：O(N)，几个存数字的数组