力扣LCP07题C语言
时间: 2025-01-30 20:08:16 浏览: 40
### LeetCode LCP07 C语言解决方案
对于LeetCode LCP07问题,即计算美丽子数组的数量,在给定的整数数组 `nums` 和非负整数 `k` 下,目标是找到满足条件 `(nums[i] XOR nums[j]) AND k == 0` 的不同下标对 (i, j),其中 i < j。此题可以通过前缀异或和哈希表来高效解决。
#### 方法概述
通过遍历整个数组并维护一个当前累积的异或值以及之前遇到过的相同累积异或值次数的映射,可以快速判断是否存在符合条件的新子数组。具体来说:
- 使用变量 `xorSum` 来保存到当前位置为止所有元素按位异或的结果;
- 对于每一个新位置上的数值,先检查 `map[xorSum & (~k)]` 是否存在,如果存在则说明找到了一个新的有效区间;
- 更新 `map[xorSum] += 1` 表示以当前位置结尾的有效区间的数量增加了一个单位;
下面是具体的实现代码[^1]:
```c
#include <stdio.h>
#include <stdlib.h>
int beautifulSubarrays(int* nums, int numsSize){
// 创建一个大小为2^20的hash table用于存储已经访问过得XOR结果及其频率
long hashTable[(1 << 20)];
// 初始化hash table全为0
memset(hashTable, 0, sizeof(long)*(1<<20));
// 设置初始状态:当没有任何元素被选入时也认为是一个有效的子序列
hashTable[0]++;
unsigned int xorSum = 0;
int resultCount = 0;
for (int index = 0 ; index < numsSize ; ++index) {
xorSum ^= nums[index];
// 计算当前XOR与K做AND运算后的值作为key去查询hash table
unsigned int key = xorSum & ((unsigned int)(~((long)k)));
// 如果该key存在于之前的记录中,则意味着有新的合法子数组出现
if (hashTable[key]){
resultCount += hashTable[key];
}
// 将当前的XOR加入到hash table里边以便后续使用
hashTable[xorSum]++;
}
return resultCount;
}
```
这段程序实现了上述逻辑,并且能够有效地找出所有的美丽子数组而不需要两层循环暴力枚举所有可能的情况。这种方法的时间复杂度接近O(n),远优于直接求解的方法。
阅读全文
相关推荐


















