计算 K 置位下标对应元素的和
难度:
标签:
题目描述
You are given a 0-indexed integer array nums and an integer k.
Return an integer that denotes the sum of elements in nums whose corresponding indices have exactly k set bits in their binary representation.
The set bits in an integer are the 1's present when it is written in binary.
- For example, the binary representation of
21is10101, which has3set bits.
Example 1:
Input: nums = [5,10,1,5,2], k = 1 Output: 13 Explanation: The binary representation of the indices are: 0 = 0002 1 = 0012 2 = 0102 3 = 0112 4 = 1002 Indices 1, 2, and 4 have k = 1 set bits in their binary representation. Hence, the answer is nums[1] + nums[2] + nums[4] = 13.
Example 2:
Input: nums = [4,3,2,1], k = 2 Output: 1 Explanation: The binary representation of the indices are: 0 = 002 1 = 012 2 = 102 3 = 112 Only index 3 has k = 2 set bits in its binary representation. Hence, the answer is nums[3] = 1.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1050 <= k <= 10
代码结果
运行时间: 12 ms, 内存: 16.1 MB
// 思路：
// 1. 使用 Java Stream API 对 nums 数组进行处理。
// 2. 利用 IntStream.range 生成下标流。
// 3. 过滤出二进制表示中置位个数为 k 的下标。
// 4. 将这些下标对应的 nums 元素相加。
import java.util.stream.IntStream;
public class Solution {
public int sumOfElementsWithKBits(int[] nums, int k) {
return IntStream.range(0, nums.length) // 生成下标流
.filter(i -> Integer.bitCount(i) == k) // 过滤出二进制表示中置位个数为 k 的下标
.map(i -> nums[i]) // 将下标映射到对应的 nums 元素
.sum(); // 将这些元素相加
}
}
解释
方法:
此题解通过遍历数组 nums 的所有下标，对每个下标 i 转换为二进制形式，并计算二进制中1的个数。如果1的个数等于 k，就将对应的 nums[i] 加入到结果和中。最终返回这个求和结果。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算下标的二进制中置位个数时选择使用 `bin(i).count('1')` 方法？是否有其他更高效的计算方法？
▷🦆
题解提到如果 `bin(i).count('1') == k` 则进行累加，对于 k 的取值范围有什么特别的要求或限制吗？
▷🦆
在实现中使用了循环遍历数组下标，如果数组长度极大，这种方法的性能如何？是否有可能通过预处理或其他技巧减少运算次数？
▷🦆
解题类中的方法是否可以处理所有输入情况，例如 k 大于数组最大下标的位数情况，会返回什么结果？
▷