在字符串题里，Add Binary 是一个非常典型、同时又非常适合考察模拟 + 指针 + 进位处理的面试题。leetcode
很多同学第一次见到时，直觉解法就是"转成十进制相加再转回二进制"，但面试官往往希望你自己模拟二进制加法的全过程。
本文会从题目、自己的初始思路（用栈）出发，一步步梳理出更接近"标准面试写法"的解法，并顺便聊聊面试官可能会怎么追问你。egbert-yu-ting.github+1
题目与示例
题目描述：leetcode
给定两个二进制字符串 a 和 b，返回它们的和（相加结果），结果也用二进制字符串表示。
示例：intervue+1
示例 1：
输入：a = “11”, b = “1”
输出：“100”
示例 2：
输入：a = “1010”, b = “1011”
输出：“10101”
约束：platformalgorithmsdatastructures.kingofinterviews+1
- 1 <= a.length, b.length <= 10^4
- a 和 b 只包含 ‘0’ 和 ‘1’
- 除了数字 0 本身，字符串中不存在前导 0
注意：长度可以到 10^4，这意味着不能转成普通整型相加，否则存在溢出风险。algo+1
初始思路：用栈模拟手算
先看一个非常自然、也完全能通过的思路：用栈来反转结果。
思路步骤
- 准备一个栈，存放每一位相加后的结果。
- 从低位到高位（从字符串末尾往前）：
- 取出当前位的 a 和 b（如果已经越界就当作 0）；
- 和当前的 carry 一起相加：sum = bitA + bitB + carry；
- 当前位结果是 sum % 2，压栈；
- 更新进位 carry = sum / 2。
- 遍历结束后，如果 carry 还为 1，再额外压栈一个 1。
- 不断弹栈，把数字 0/1 转成字符 ‘0’/‘1’ 拼接成结果字符串。
复杂度分析
- 时间复杂度：O(n+m)，其中 n 和 m 是两个字符串长度。algomap
- 空间复杂度：O(n+m)（栈中存下了所有位）。algomap
这个解法在面试中绝对是"正确解"，不会被一票否决。真正的区别在于：你能不能在面试官轻轻一提的情况下，往更优、更简洁的写法走一步。
面试官视角：会追问什么？
你说完上面栈的思路后，面试官很可能会顺着这几个方向提问：
1. “一定要用栈吗？”
这一问的核心是：你是否意识到栈只是帮你反转顺序。
你现在是「从低位往高位算」→ 结果低位先拿到 → 用栈反过来。
但是反转有很多方式，比如：
- 可以先把结果存在一个数组或字符串里，最后整体反转；
- 可以使用 StringBuilder 前插（insert(0, …)），虽然有时效率稍差。
这时，如果你能自然说出"其实栈不是必须的，我也可以用双指针 + StringBuilder，然后最后反转"的版本，就会显得思路更加抽象、清晰。
2. “空间还能再省一点吗？”
这里的考点是：你能否把额外空间降到 O(1)（不算返回结果本身）。dev+1
遍历时只需要：
- 两个指针 i, j；
- 一个整型 carry；
- 一个用来构建最终结果的 StringBuilder 或字符串。
不再需要栈这种额外的数据结构。
3. “大输入会不会溢出？”
如果你一开始说的是 int(a, 2) + int(b, 2) 这种写法，面试官几乎一定会追问：
- 这个方法对 10^4 长度的二进制字符串安全吗？
- 如果语言是 Java、C++，用 int / long 会发生什么？
所以更稳妥的回答是：题目长度上限很大，不能依赖内置整数类型，需要自己模拟按位加法。algo+1
更"标准"的写法：双指针 + 进位 + 反转
下面是把你"栈思路"小幅演化后，在面试中非常常见、也更推荐的一版：
核心思想
使用两个指针：
- i = a.length - 1 指向 a 的最低位；
- j = b.length - 1 指向 b 的最低位。
初始化 carry = 0。
循环条件写成：
while (i >= 0 || j >= 0 || carry != 0)每次循环：
- sum = carry；
- 如果 i >= 0，sum += a[i] - ‘0’，然后 i–；
- 如果 j >= 0，sum += b[j] - ‘0’，然后 j–；
- 当前位结果 sum % 2 加入结果字符串；
- 更新 carry = sum / 2。
最终把结果字符串整体 reverse 一下，就是答案。dev+1
伪代码（类 C++ / Java 风格）
function addBinary(a, b): i = a.length - 1 j = b.length - 1 carry = 0 result = 空字符串（或 StringBuilder） while i >= 0 or j >= 0 or carry != 0: sum = carry if i >= 0: sum += (a[i] - '0') i -= 1 if j >= 0: sum += (b[j] - '0') j -= 1 bit = sum % 2 carry = sum / 2 // 整除 // 因为是从低位往高位算，可以先拼在尾部，最后再反转 result.append(字符(bit + '0')) // 现在 result 是反过来的，需要整体反转 reverse(result) return result.toString()复杂度
- 时间复杂度：O(n+m)，只遍历一遍两个字符串。dev+1
- 空间复杂度：额外空间 O(1)，只使用常数个变量（不计返回字符串）。algomap+1
和"用栈"的版本对比，两者在时间上是一样的，区别在于空间更精简，代码也更符合常见模板，更像你已经刷过一圈题之后的写法。
实战中容易踩的坑
做这题时，有几个细节很容易出错：
越界处理
当 i < 0 或 j < 0 时，应该把对应位当作 0，而不是直接访问数组。
循环条件写得不严谨
如果写成 while (i >= 0 || j >= 0)，最后 carry 可能还为 1，但你已经退出循环了。
最安全的是：
while (i >= 0 || j >= 0 || carry != 0)字符与数字之间的转换
- 获取当前位：a[i] - ‘0’，b[j] - ‘0’。
- 拼回字符：bit + ‘0’。
结果反转忘记
从低位算到高位，如果你是一直 append 到字符串尾部，最后一定要 reverse 一次。
总结：从"能做出来"到"写得漂亮"
从这道题可以看到一个常见的进阶路径：
第一步：
能想到用栈从低位到高位模拟，说明对进位加法的本质已经理解到位；
第二步：
意识到"栈只是为了反转"，可以被 StringBuilder + reverse 等方式替代；
第三步：
自然写出"双指针 + carry + 一次遍历"的版本，时间 O(n + m)，空间 O(1)，并能清晰讲出边界和复杂度。
如果你已经有了"用栈"的初始版本，非常建议下一步自己手写一遍双指针版本，重点训练：
- while 条件；
- 越界时的处理；
- 字符与数字的转换。
