Easy

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

请你返回 nums 中下标对应的二进制表示中恰好有 k 个置位的元素的和。

整数的置位是指二进制表示中的 1。

  • 例如，21 的二进制表示为 10101，有 3 个置位。

示例 1：

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示如下：
0 = 000₂
1 = 001₂ 
2 = 010₂
3 = 011₂
4 = 100₂
下标 1、2 和 4 在二进制表示中都恰好有 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

示例 2：

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示如下：
0 = 00₂
1 = 01₂
2 = 10₂
3 = 11₂
只有下标 3 在二进制表示中恰好有 k = 2 个置位。
因此，答案为 nums[3] = 1 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10⁵
  • 0 <= k <= 10

解题思路

这道题需要我们找到所有下标的二进制表示中恰好有 k 个置位（1的个数）的位置，然后将对应的数组元素相加。

解题思路：

  1. 遍历数组下标：从 0 到 n-1 遍历所有可能的下标
  2. 计算置位数：对每个下标计算其二进制表示中 1 的个数
  3. 累加符合条件的元素：如果置位数等于 k，则将对应的数组元素加到结果中

计算置位数的方法：

  • 方法一：使用内置函数（如 __builtin_popcount、bin().count('1') 等）
  • 方法二：使用位运算技巧，通过 n & (n-1) 操作逐个清除最低位的 1
  • 方法三：逐位检查，通过右移和按位与操作

由于题目限制数组长度最大为 1000，所以下标最大不超过 999，其二进制表示最多 10 位，任何方法都能高效处理。这里推荐使用内置函数，代码简洁且效率高。

算法流程简单直观：遍历 → 计算置位数 → 判断 → 累加。时间复杂度主要取决于遍历数组的次数。

代码实现

class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (__builtin_popcount(i) == k) {
                sum += nums[i];
            }
        }
        return sum;
    }
};

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        return sum(nums[i] for i in range(len(nums)) if bin(i).count('1') == k)

public class Solution {
    public int SumIndicesWithKSetBits(IList<int> nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.Count; i++) {
            if (System.Numerics.BitOperations.PopCount((uint)i) == k) {
                sum += nums[i];
            }
        }
        return sum;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumIndicesWithKSetBits = function(nums, k) {
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i.toString(2).split('1').length - 1 === k) {
            sum += nums[i];
        }
    }
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)遍历数组 O(n)，每次计算置位数 O(log i)，总体 O(n log n)
空间复杂度O(1)只使用常数级别的额外空间

相关题目