题目

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1" 输出："100"

示例 2：

输入：a = "1010", b = "1011" 输出："10101"

提示：

• 1 <= a.length, b.length <= 10^4
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

解题思路

因为题目限制字符串长度可达 $10^4$，这远远超过了 int64 能表示的范围（64位），所以直接转换成整数相加会发生溢出。

我们需要模拟我们在纸上做“竖式加法”的过程：从低位向高位遍历，处理进位。

核心逻辑

1. 对齐： 使用两个指针 $i$ 和 $j$ 分别指向字符串 $a$ 和 $b$ 的末尾（最低位）。
2. 循环： 只要指针没有越界，或者 carry（进位）不为 0，就继续循环。
   • 取值：如果指针合法，取出当前位的数字（0 或 1）；如果越界，视为 0。
   • 求和：sum = valA + valB + carry。
   • 结果位：sum % 2 是当前位的值。
   • 新进位：sum / 2 是下一位的进位。
3. 拼接： 将结果位拼接到最终字符串中。
4. 反转： 因为我们是从低位算到高位（从后往前），拼接出来的字符串是反的，最后需要反转一次。

具体代码

func addBinary(a string, b string) string {
    // 1. 初始化结果容器
    // 预分配容量：取较长字符串长度 + 1 (可能的最高位进位)
    // 这样做可以避免 append 时的多次内存扩容
    n := max(len(a), len(b))
    ans := make([]byte, 0, n+1)

    // 2. 双指针倒序遍历
    i, j := len(a)-1, len(b)-1
    carry := 0

    // 循环条件：只要 a 或 b 还有位没遍历完，或者还有进位需要处理
    for i >= 0 || j >= 0 || carry > 0 {
        sum := carry

        // 处理 a 的当前位
        if i >= 0 {
            sum += int(a[i] - '0') // 字符 '1' -> 数字 1
            i--
        }

        // 处理 b 的当前位
        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }

        // 当前位的结果放入 ans (注意：这里是逆序放入的)
        ans = append(ans, byte(sum%2+'0'))

        // 计算新的进位
        carry = sum / 2
    }

    // 3. 反转结果
    // 因为是从低位算到高位 append 的，所以结果是反的，需要 reverse
    reverse(ans)

    return string(ans)
}

// 辅助函数：反转 byte 切片
func reverse(b []byte) {
    left, right := 0, len(b)-1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}