LeetCode 2859. 计算 K 置位下标对应元素的和

在本篇文章中，我们将探讨如何求解 LeetCode 上的 2859. 计算 K 置位下标对应元素的和问题。这个问题要求我们找到一个数组中特定元素的和，这些特定元素的下标在二进制表示中恰好有 k 个置位。

问题描述

 

算法分析

为了解决这个问题，我们可以采用以下步骤：

1. 计算置位数量：对于每个下标，计算其二进制表示中 1 的个数。

2. 检查条件：如果置位数量等于 k，则将对应元素加到总和中。

代码实现

以下是使用 C++ 实现的代码：

#include <vector>class Solution {
public:int sumIndicesWithKSetBits(std::vector<int>& nums, int k) {int n = nums.size();int sum = 0;// 遍历数组numsfor (int i = 0; i < n; i++) {// 计算当前下标的二进制表示中1的个数int count = 0;int temp = i;while (temp > 0) {count += temp & 1;temp >>= 1;}// 如果1的个数等于k，则将对应元素加到sum中if (count == k) {sum += nums[i];}}return sum;}
};

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是数组 nums 的长度，m 是计算每个下标二进制表示中 1 的个数所需的时间。在最坏情况下，m 可以接近于 log2(n)。

• 空间复杂度：O(1)，我们只需要常数额外空间。

结论

通过计算每个下标的二进制表示中 1 的个数，并检查是否等于 k，我们可以找到满足条件的元素并计算它们的和。这种方法简单且有效，适用于处理大规模数据。