当前位置：首页 > article >正文

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

article 2025/2/3 4:10:40

本文涉及知识点

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

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);
		}