LeetCode 67. 二进制求和

约 5 分钟
文章信息 12 个分类 6 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 微软 快手 腾讯 拼多多 亚马逊 面试经典 150 题
标签
字符串 数学 位运算 模拟 数学经典题 加法问题
目录

题目描述

✅ 67. 二进制求和

image-20230312123807986

题意分析

给定两个只由字符 '0' 和 '1' 组成的字符串 a 和 b，它们各自表示一个非负二进制数，要求返回它们之和，同样用二进制字符串表示。

输入输出都是字符串而不是数字，这是全题最重要的信号。约束里写明两个串的长度可以到 $10^4$，一个 $10^4$ 位的二进制数量级在 $2^{10^4}$ 上下，比宇宙里的原子数还大出天文数字倍，任何定长整数类型都装不下。所以「先转成整数、加完再转回去」这条路在本题是被约束直接堵死的，只能老老实实按字符处理。

题目还保证输入不含多余的前导零——除非这个数本身就是 "0"。这意味着两件事："0" 是合法输入，必须能正确处理；输出也应该遵循同样的规范，不带多余前导零。

两个串的长度可以不相等，短的那个在高位方向上「用完」之后，对应位应当按 0 参与运算，而不是提前终止整个过程。

需要单独想清楚的边界：某个串是 "0"；两串长度差距很大；全是 1 导致进位一路从最低位串到最高位；以及最高位相加之后仍有进位，此时结果会比更长的那个输入还多出一位。

解法：双指针模拟竖式加法

核心思路

输入可能有上万位，不能先转成整数。直接模拟二进制竖式加法：两个指针从字符串末尾向前移动，用 carry 保存低位产生的进位。

每轮只依赖 a[i]、b[j] 和 carry。当前位写入 sum % 2，下一位进位更新为 sum / 2。某个字符串先耗尽时，该侧按 0 处理。

循环不变量是：缓冲区中已经生成的字符，正好是答案从低到高的若干位；carry 是这些低位向尚未处理高位产生的唯一进位。循环结束后反转缓冲区即可。

解题步骤

  1. 令 i、j 分别指向两个字符串的末尾，carry = 0。
  2. 当任一字符串还有字符，或仍有进位时继续循环。
  3. 把两个当前位和进位相加，追加 sum % 2，再令 carry = sum / 2。
  4. 两个指针各自左移；短字符串越界后不再提供数位。
  5. 反转缓冲区并返回。

例如 1010 + 1011 从低位开始依次生成 1、0、1、0、1，反转后得到 10101。

代码实现

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder result = new StringBuilder(Math.max(a.length(), b.length()) + 1);

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            result.append(sum % 2);
            carry = sum / 2;
        }
        return result.reverse().toString();
    }
}

func addBinary(a string, b string) string {
    i, j, carry := len(a)-1, len(b)-1, 0
    result := make([]byte, 0, max(len(a), len(b))+1)

    for i >= 0 || j >= 0 || carry != 0 {
        sum := carry
        if i >= 0 {
            sum += int(a[i] - '0')
            i--
        }
        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }
        result = append(result, byte(sum%2)+'0')
        carry = sum / 2
    }
    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }
    return string(result)
}

复杂度分析

  • 时间复杂度：$O(\max(m,n))$，逐位处理较长输入，并线性反转同等长度的结果。
  • 空间复杂度：$O(\max(m,n))$，用于保存返回字符串；不计返回值时额外空间为 $O(1)$。

关键点总结

  • 字符串表示的大整数不能依赖定长整数类型，逐位运算才不受位数限制。
  • 循环条件必须包含 carry != 0，否则可能丢掉最高位进位。
  • 结果按低位到高位生成，统一反转比不断在字符串头部插入更高效。
  • 二进制中 sum 最大为 3，因此进位始终只有 0 或 1。

易错点总结

  • 只在两个指针未越界时循环，会漏掉最后一个进位。
  • 忘记把字符减 '0'，会把字符编码当成数值参与计算。
  • 忘记反转，会得到位序颠倒的字符串。
  • 在循环中用 digit + result 头插字符串，会因反复复制退化为 $O(n^2)$。

相似题目

题目 难度 考察点
2. 两数相加 中等 链表上的进位模拟
43. 字符串相乘 中等 大数竖式乘法
66. 加一 简单 数组末位进位传播
371. 两整数之和 中等 位运算实现加法
415. 字符串相加 简单 十进制大数加法
989. 数组形式的整数加法 简单 数组与整数混合相加
1073. 负二进制数相加 中等 负进制下的进位规则
LCR 002. 二进制求和 简单 二进制求和同题变体