【C++ 区间位运算】3209. 子数组按位与值为 K 的数目|2050

本文涉及知识点

位运算、状态压缩、枚举子集汇总

LeetCode3209. 子数组按位与值为 K 的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组
满足：子数组中所有元素按位 AND 的结果为 k 。
示例 1：
输入：nums = [1,1,1], k = 1
输出：6
解释：
所有子数组都只含有元素 1 。
示例 2：
输入：nums = [1,1,2], k = 1
输出：3
解释：
按位 AND 值为 1 的子数组包括：[1,1,2], [1,1,2], [1,1,2] 。
示例 3：
输入：nums = [1,2,3], k = 2
输出：2
解释：
按位 AND 值为 2 的子数组包括：[1,2,3], [1,2,3] 。
提示：
1 <= nums.length <= 10⁵
0 <= nums[i], k <= 10⁹

代码

核心代码

class CRangCal {
public:template<class _Pr, class T = int>static vector<vector<pair<T, int>>> RangCal(const vector<T>& nums, _Pr pr) {vector<vector<pair<int, int>>> vNumIndex(nums.size());for (int i = 0; i < nums.size(); i++) {if (i) {for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {auto iNew = pr(preNum, nums[i]);if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {vNumIndex[i].emplace_back(make_pair(iNew, preIndex));}else {vNumIndex[i].back().second = preIndex;}}}if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {vNumIndex[i].emplace_back(make_pair(nums[i], i));}else {vNumIndex[i].back().second = i;}}return vNumIndex;}
};class Solution {public:long long countSubarrays(vector<int>& nums, int k) {auto res =	CRangCal::RangCal(nums, [&](int n1, int n2) {return n1 & n2; });long long ans = 0;int i = -1;for (const auto& v : res) {i++;for (int j = 0; j < v.size(); j++) {if (v[j].first == k) {		const int begin = (0 == j) ? -1 : v[j - 1].second;ans += (v[j].second-begin);}}}return ans;}};

单元测试

vector<int> nums;int k;TEST_METHOD(TestMethod11){nums = { 1, 1, 1 }, k = 1;auto res = Solution().countSubarrays(nums, k);AssertEx(6LL, res);}TEST_METHOD(TestMethod12){nums = { 1, 1, 2 }, k = 1;auto res = Solution().countSubarrays(nums, k);AssertEx(3LL, res);}TEST_METHOD(TestMethod13){nums = { 1, 2, 3 }, k = 2;auto res = Solution().countSubarrays(nums, k);AssertEx(2LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《

算法与数据汇总》。|
学习算法：

按章节学习《喜缺全书算法册》，大量

的题目和测试用例，打包下载。重

视操作|
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
|闻缺陷则喜(喜缺)是一个美好的

愿望，早发现问题，早修改问题，给老板节约钱。|
| 子墨子言之：事无终始，无务多业。也就是我们

常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
|失败+反思=成功 成功+反

思=成功|

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你

想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系

统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特

殊说明，本算法用**C++**实现。