LeetCode 补充题 21. 字符串相减
目录
题目描述
✅ 补充题 21. 字符串相减
题意分析
给两个用字符串表示的十进制非负整数
num1、num2，返回num1 - num2的十进制字符串结果。要什么：一个字符串形式的差。和「字符串相加」不同的是，减法的结果可能为负，所以返回值可能带一个前缀
-。约束信号：题目强调用字符串给数字，就是在明说这两个数可能长到几千甚至上万位，远超
int的 10 位、long的 19 位。任何parseLong、atoi的写法都是在绕开考点，必须老老实实按位模拟。另一个信号是输入是纯十进制数字串，没有小数点、没有正负号，所以不用做通用的字符串解析。边界要提前列清楚，这题的失分几乎全在边界上：输入可能带前导零（
"0012"就是 12）；两数相等时结果是"0"而不是空串或"-0"；num1 < num2时结果为负；num2可能比num1短很多，短的那一位要当 0 补齐；借位可能连续传播很多位，比如"10000" - "1"；相减完成后高位会留下一串前导零（"100" - "99"的逐位结果是"001"），必须再清理一次。顺带一提，题目只要求差值，不要求处理负数输入，也不要求保留输入的前导零格式。
解法：逐位借位模拟
核心思路
输入可能超过整数范围，直接按小学竖式从低位向高位相减。为让主循环始终处理「大数减小数」，先去掉前导零并比较绝对值；若
num1 < num2，交换二者并记录负号。扫描不变量是：结果缓冲区逆序保存已经确定的低位，
borrow表示当前位还欠高位的 1。每轮计算digit = 当前位 - borrow；若它小于减数当前位，就加 10 并继续借位，否则清零借位。绝对值较大的一方处理完后不会再欠借位。反转结果、清除运算产生的前导零，再补符号即可。两数相等提前返回
"0"，避免-0。
解题步骤
- 去掉两个输入的前导零；相等则返回
"0"。- 先按长度、再按字典序比较。若第一个数较小，交换两数并记录结果为负。
- 从右向左逐位相减，短串缺失的高位按 0 处理；当前位不够减就加 10，并令
borrow = 1。- 反转缓冲区，去掉结果前导零，最后按标记添加负号。
例如
1000 - 1：低位连续借位得到逆序结果9990，反转并去零后为999。该用例同时覆盖连续借位、短串补零和结果清零。
代码实现
class Solution {
public String subtract(String num1, String num2) {
num1 = stripLeadingZeros(num1);
num2 = stripLeadingZeros(num2);
if (num1.equals(num2)) {
return "0";
}
boolean negative = false;
if (compare(num1, num2) < 0) {
String value = num1;
num1 = num2;
num2 = value;
negative = true;
}
StringBuilder builder = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int borrow = 0;
while (i >= 0) {
int digit = num1.charAt(i) - '0' - borrow;
int subtrahend = j >= 0 ? num2.charAt(j) - '0' : 0;
// 当前位不够减时向高位借 1，本位实际加 10。
if (digit < subtrahend) {
digit += 10;
borrow = 1;
} else {
borrow = 0;
}
builder.append(digit - subtrahend);
i--;
j--;
}
String result = stripLeadingZeros(builder.reverse().toString());
if (negative) {
return "-" + result;
}
return result;
}
private int compare(String first, String second) {
if (first.length() != second.length()) {
return first.length() - second.length();
}
return first.compareTo(second);
}
private String stripLeadingZeros(String value) {
int idx = 0;
while (idx + 1 < value.length() && value.charAt(idx) == '0') {
idx++;
}
return value.substring(idx);
}
}
func subtract(num1 string, num2 string) string {
num1 = stripLeadingZeros(num1)
num2 = stripLeadingZeros(num2)
if num1 == num2 {
return "0"
}
negative := false
if compareDecimalStrings(num1, num2) < 0 {
num1, num2 = num2, num1
negative = true
}
digits := make([]byte, 0, len(num1))
i, j := len(num1)-1, len(num2)-1
borrow := 0
for i >= 0 {
digit := int(num1[i]-'0') - borrow
subtrahend := 0
if j >= 0 {
subtrahend = int(num2[j] - '0')
}
// 当前位不够减时向高位借 1，本位实际加 10。
if digit < subtrahend {
digit += 10
borrow = 1
} else {
borrow = 0
}
digits = append(digits, byte(digit-subtrahend)+'0')
i--
j--
}
for left, right := 0, len(digits)-1; left < right; left, right = left+1, right-1 {
digits[left], digits[right] = digits[right], digits[left]
}
result := stripLeadingZeros(string(digits))
if negative {
return "-" + result
}
return result
}
func compareDecimalStrings(first string, second string) int {
if len(first) != len(second) {
return len(first) - len(second)
}
for idx := 0; idx < len(first); idx++ {
if first[idx] != second[idx] {
return int(first[idx]) - int(second[idx])
}
}
return 0
}
func stripLeadingZeros(value string) string {
idx := 0
for idx+1 < len(value) && value[idx] == '0' {
idx++
}
return value[idx:]
}
复杂度分析
- 时间复杂度：$O(n + m)$，每个输入只被常数次线性扫描。
- 空间复杂度：$O(\max(n,m))$，用于结果缓冲区。
关键点总结
- 先统一成绝对值较大的数减较小的数，符号只在末尾处理。
- 借位必须先从当前位扣除，并在每轮明确更新为 0 或 1。
- 输入去零用于正确比较，输出去零用于规范结果，两次都需要。
- 面试应主动覆盖：相等、负结果、连续借位、输入和输出前导零。
易错点总结
- 用
long转换会在超长输入上溢出，失去字符串运算的意义。- 等长前可以按字典序比较；长度不等时必须先比较长度，如
9 < 10。- 忘记扣上一位借位会把
100 - 1算错。- 去前导零时至少保留一个字符，否则
"0"会变成空串。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 2. 两数相加 | 中等 | 链表形式的逐位进位 |
| 43. 字符串相乘 | 中等 | 大数乘法的错位累加 |
| 66. 加一 | 简单 | 数组上的进位传播 |
| 67. 二进制求和 | 简单 | 二进制下的逐位相加 |
| 415. 字符串相加 | 简单 | 大数加法，本题的镜像版本 |