LeetCode 477. 汉明距离总和

2025-04-16 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 477. 汉明距离总和

题意分析

汉明距离指两个数在二进制表示下对应位不同的位数。题目要求把数组中所有数对的汉明距离加起来，每对只算一次（无序对）。

「求所有数对某种度量之和」是一个强信号：它提示我们不要真的去枚举数对，而应该找一个能把总和拆成独立部分的角度。

汉明距离本身天然可拆：两个数的距离等于它们在第 0 位是否不同、第 1 位是否不同、……逐位加起来。而求和可以交换次序——先对位求和再对数对求和，等于先对数对求和再对位求和。这一步交换是整道题的关键，它把「对每一对数看所有位」翻转成「对每一位看所有数对」。

数据规模上数组长度可达 10^4，元素取值范围是 $[0, 10^9]$。长度 10^4 意味着数对有约 5×10^7 个，逐对计算再逐位比较会到 10^9 量级，太慢。取值上界 10^9 小于 $2^{30}$，所以只需考虑第 0 到第 30 位共 31 位，且所有元素非负，不必操心符号位。

边界包括：数组只有一个元素时不存在任何数对，答案为 0；所有元素相同时答案也是 0；某一位上全是 1 或全是 0 时该位贡献为 0。

解法：按位计数

核心思路

暴力做法是双重循环枚举所有数对，对每对做 Integer.bitCount(a ^ b)。正确，但数对数量是 $\binom{n}{2}$，在 10^4 长度下约 5×10^7 对，每对还要做一次位计数，整体逼近 10^9 次操作，会超时。瓶颈在于同一位上的信息被重复计算了千万次。

换个角度。把总和写成双重求和并交换次序：
\[\sum_{i<j} d(nums_i, nums_j) = \sum_{i<j} \sum_{b=0}^{30} [\text{第 } b \text{ 位不同}] = \sum_{b=0}^{30} \sum_{i<j} [\text{第 } b \text{ 位不同}]\]
交换之后，内层要回答的问题变成：固定第 b 位，有多少对数在这一位上取值不同。这个问题极其简单——设这一位上有 ones 个数取 1，那么取 0 的就有 n - ones 个。一对数在该位不同，当且仅当一个来自 1 组、另一个来自 0 组，所以恰好有 ones × (n - ones) 对。

注意这个乘积天然就是无序对的数量，不需要再除以 2：因为两个组是不相交的，从 1 组取一个、从 0 组取一个，每种组合只会被数一次，不存在「正反各算一遍」的问题。这一点与「从同一集合里取两个」的场景不同，是这道题最容易被误改的地方。

于是不变量表述为：处理完第 b 位后，total 恰好等于所有数对在第 0 到第 b 位上的差异位数总和。逐位累加到第 30 位，就得到完整答案。

位数上界取 31 是由值域 $10^9 < 2^{30}$ 决定的：最高有效位是第 29 位（$2^{29} \approx 5.4 \times 10^8$）到第 30 位（$2^{30} \approx 1.07 \times 10^9$），扫到 30 足够覆盖；更高的位上所有数都是 0，ones 恒为 0，贡献必然为 0，扫不扫都不影响结果。

解题步骤

记录数组长度 n，初始化答案 total = 0。之所以需要 n，是因为每一位的贡献公式里要用它算出 0 的个数。

外层循环遍历位号 bit 从 0 到 30。之所以以位为外层、数为内层，是因为每一位的统计彼此独立，这个顺序让 ones 计数器在一位处理完后可以立即清零复用，不需要开数组。

内层遍历所有元素，用 (num >> bit) & 1 取出该位并统计 ones。之所以用右移再与 1，而不是与一个掩码 1 << bit 后判非零，是因为前者直接得到 0 或 1 可以参与算术，后者还要额外转换；两种写法都对，前者更省一次分支。

累加 ones * (n - ones) 到 total。之所以不除以 2，是因为 1 组和 0 组不相交，乘法本身已经是无序对的精确计数。

全部位处理完后返回 total。

以 nums = [4, 14, 2] 走一遍，n = 3，预期答案是 6（d(4,14) = 2、d(4,2) = 2、d(14,2) = 2）。三个数的二进制分别是 00100、01110、00010。

bit = 0：三个数的最低位分别是 0、0、0，ones = 0，贡献 0 * 3 = 0。

bit = 1：三个数的第 1 位分别是 0、1、1，ones = 2，贡献 2 * (3 - 2) = 2。含义是：14 和 2 这两个「取 1」的数，各自与 4 这个「取 0」的数在该位不同，共两对。

bit = 2：三个数的第 2 位分别是 1、1、0，ones = 2，贡献 2 * 1 = 2。

bit = 3：三个数的第 3 位分别是 0、1、0，ones = 1，贡献 1 * 2 = 2。

bit = 4 及以上：三个数在这些位上全为 0，ones = 0，贡献恒为 0。

累加得 0 + 2 + 2 + 2 = 6，与预期一致。

再用 nums = [7] 检验边界：n = 1，无论哪一位，ones 要么是 0 要么是 1，对应的贡献是 0 * 1 = 0 或 1 * 0 = 0，全部为 0，返回 0，正确——单个元素构不成任何数对。

代码实现

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int total = 0;

        for (int bit = 0; bit < 31; bit++) {
            int ones = 0;
            for (int num : nums) {
                if (((num >> bit) & 1) == 1) {
                    ones++;
                }
            }
            total += ones * (n - ones);
        }

        return total;
    }
}

func totalHammingDistance(nums []int) int {
    n := len(nums)
    total := 0

    for bit := 0; bit < 31; bit++ {
        ones := 0
        for _, num := range nums {
            if (num>>bit)&1 == 1 {
                ones++
            }
        }
        total += ones * (n - ones)
    }

    return total
}

复杂度分析

时间复杂度：$O(31n)$，即 $O(n)$，凭据是外层固定跑 31 轮（由值域上界 $10^9 < 2^{30}$ 决定，与输入规模无关），内层每轮扫一遍数组做常数次位运算，两层相乘后位数是常数因子。

空间复杂度：$O(1)$，凭据是全程只维护 n、total、ones 和两个循环变量，没有开任何与数组长度相关的辅助结构，ones 在每一位处理完后被复用。

关键点总结

「所有数对的某种度量之和」这类问题，优先尝试交换求和次序：把「对每一对看所有维度」翻成「对每一维看所有对」，往往能让内层退化成一个可以 $O(1)$ 或 $O(n)$ 解决的计数问题。

汉明距离、曼哈顿距离这类「可按维度分解」的度量天生适配上述交换；判断一个度量能不能这么拆，看它是否等于各维度独立贡献之和。

「一组取一个、另一组取一个」的配对数就是两组大小的乘积，不需要除以 2；只有「从同一组里取两个」才需要用 $\binom{k}{2}$。混淆这两种情形是这类计数题的头号错误。

位数上界应由值域推出而不是随手写 32：本题非负且不超过 $10^9$，扫到第 30 位即可；扫多几位不会错但会白跑，扫少了则直接漏算。

每一位的统计彼此独立，因此外层按位、内层按数的循环顺序能让计数器复用，把空间压到常数。

面试视角：面试官会先让你说出 $O(n^2 \cdot 31)$ 的暴力，然后问「能不能不枚举数对」。答题时要把求和交换那一步显式写出来，这是评分的核心；随后主动说明「为什么乘积不用除以 2」，通常能挡掉后续追问。若被问到溢出，可以指出 n = 10^4 时单位贡献上界是 $2.5 \times 10^7$、31 位合计约 $7.75 \times 10^8$，仍在 int 范围内。

易错点总结

把贡献写成 ones * (n - ones) / 2：用例 nums = [4, 14, 2]，每位贡献被砍半且整除截断，返回 3 而非 6；乘积已经是无序对数量，再除以 2 是重复修正。

把贡献写成 ones * (ones - 1) / 2：用例 nums = [4, 14, 2]，统计的是「两个数在该位都为 1」的对数，与「该位不同」完全无关，返回 0。

位循环上界写成 bit < 30：用例 nums = [1073741824, 0]（即 $2^{30}$ 与 0），第 30 位的差异被漏掉，返回 0 而非 1。

位循环上界写成 bit < 32 且用 int 处理负数：本题元素非负不受影响，但若元素含负数，第 31 位（符号位）在算术右移下会被填充成全 1，ones 统计失真；处理有符号数时应改用无符号右移。

取位写成 num & (1 << bit) 后直接 ones += num & (1 << bit)：用例 nums = [4]，bit = 2 时加的是 4 而不是 1，ones 被放大成位权，贡献完全错误；必须先归一化成 0 或 1。

内外循环调换成「外层遍历数、内层遍历位」却仍用单个 ones 变量：用例任意输入，不同位的计数被混在一起，结果无意义；调换顺序必须改用长度 31 的计数数组。

双重循环枚举数对再 Integer.bitCount(a ^ b)：用例长度 10^4 的数组，约 5×10^7 对乘以位计数开销，超时。

忘记 ones 在每一位开始时清零：用例 nums = [1, 2]，第 1 位的计数叠加了第 0 位的残留，贡献偏大，返回 4 而非 2。

认为答案需要用 long：用例 n = 10^4 全部互补的数组，单位贡献最大为 5000 * 5000 = 2.5×10^7，31 位合计约 7.75×10^8，未超 int 上限；无谓改成 long 不算错，但据此认为原代码有溢出 bug 会误判。

用 num >> bit % 2 这种依赖运算符优先级的写法：用例任意输入，% 优先级高于 >>，实际算的是 num >> (bit % 2)，只会取到第 0 或第 1 位，结果全错。

相似题目

题目	难度	考察点
461. 汉明距离	简单	只求单对距离，异或后数 1 即可，无需交换求和次序
191. 位1的个数	简单	单个数的位计数，考察 `n & (n-1)` 消最低位 1 的技巧
338. 比特位计数	简单	批量求位计数，用 `dp[i] = dp[i>>1] + (i&1)` 的递推加速
201. 数字范围按位与	中等	同样逐位分析，但结论是求两端的公共前缀而非按位计数
260. 只出现一次的数字 III	中等	用异或结果的某一位把数组分成两组，是按位分组思想的另一应用