class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
}
};
100338. 子数组按位与值为 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 <= 1050 <= nums[i], k <= 109原站题解
golang 解法, 执行用时: 83 ms, 内存消耗: 8.1 MB, 提交时间: 2024-07-09 10:28:46
func countSubarrays(nums []int, k int) (ans int64) {
cnt := 0
for i, x := range nums {
if x == k {
cnt++
}
for j := i - 1; j >= 0 && nums[j]&x != nums[j]; j-- {
if nums[j] == k {
cnt--
}
nums[j] &= x
if nums[j] == k {
cnt++
}
}
ans += int64(cnt)
}
return
}
// 三指针
func countSubarrays3(nums []int, k int) (ans int64) {
left, right := 0, 0
for i, x := range nums {
for j := i - 1; j >= 0 && nums[j]&x != nums[j]; j-- {
nums[j] &= x
}
for left <= i && nums[left] < k {
left++
}
for right <= i && nums[right] <= k {
right++
}
ans += int64(right - left)
}
return
}
// 二分查找
func countSubarrays2(nums []int, k int) (ans int64) {
for i, x := range nums {
for j := i - 1; j >= 0 && nums[j]&x != nums[j]; j-- {
nums[j] &= x
}
a := nums[:i+1]
ans += int64(sort.SearchInts(a, k+1) - sort.SearchInts(a, k))
}
return
}
java 解法, 执行用时: 8 ms, 内存消耗: 61.4 MB, 提交时间: 2024-07-09 10:27:18
public class Solution {
public long countSubarrays(int[] nums, int k) {
long ans = 0;
int left = 0;
int right = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
nums[j] &= x;
}
while (left <= i && nums[left] < k) {
left++;
}
while (right <= i && nums[right] <= k) {
right++;
}
ans += right - left;
}
return ans;
}
// 维护等于 k 的子数组个数
public long countSubarrays2(int[] nums, int k) {
long ans = 0;
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
cnt += x == k ? 1 : 0;
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
cnt -= nums[j] == k ? 1 : 0;
nums[j] &= x;
cnt += nums[j] == k ? 1 : 0;
}
ans += cnt;
}
return ans;
}
}
java 解法, 执行用时: 83 ms, 内存消耗: 61.8 MB, 提交时间: 2024-07-09 10:26:39
public class Solution {
public long countSubarrays(int[] nums, int k) {
long ans = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
nums[j] &= x;
}
ans += lowerBound(nums, i + 1, k + 1) - lowerBound(nums, i + 1, k);
}
return ans;
}
// https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(int[] nums, int right, int target) {
int left = -1; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // 范围缩小到 (mid, right)
} else {
right = mid; // 范围缩小到 (left, mid)
}
}
return right;
}
}
cpp 解法, 执行用时: 113 ms, 内存消耗: 91.6 MB, 提交时间: 2024-07-09 10:26:23
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
long long ans = 0;
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
cnt += x == k;
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
cnt -= nums[j] == k;
nums[j] &= x;
cnt += nums[j] == k;
}
ans += cnt;
}
return ans;
}
long long countSubarrays2(vector<int>& nums, int k) {
long long ans = 0;
int left = 0, right = 0;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
nums[j] &= x;
}
while (left <= i && nums[left] < k) {
left++;
}
while (right <= i && nums[right] <= k) {
right++;
}
ans += right - left;
}
return ans;
}
long long countSubarrays3(vector<int>& nums, int k) {
long long ans = 0;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
nums[j] &= x;
}
ans += upper_bound(nums.begin(), nums.begin() + i + 1, k) -
lower_bound(nums.begin(), nums.begin() + i + 1, k);
}
return ans;
}
};
python3 解法, 执行用时: 549 ms, 内存消耗: 24.9 MB, 提交时间: 2024-07-09 10:24:15
class Solution:
# 二分查找
def countSubarrays(self, nums: List[int], k: int) -> int:
ans = 0
for i, x in enumerate(nums):
for j in range(i - 1, -1, -1):
if nums[j] & x == nums[j]:
break
nums[j] &= x
ans += bisect_right(nums, k, 0, i + 1) - bisect_left(nums, k, 0, i + 1)
return ans
# 三指针
def countSubarrays2(self, nums: List[int], k: int) -> int:
ans = left = right = 0
for i, x in enumerate(nums):
for j in range(i - 1, -1, -1):
if nums[j] & x == nums[j]:
break
nums[j] &= x
while left <= i and nums[left] < k:
left += 1
while right <= i and nums[right] <= k:
right += 1
ans += right - left
return ans
# 维护等于k的子数组个数
def countSubarrays3(self, nums: List[int], k: int) -> int:
ans = cnt = 0
for i, x in enumerate(nums):
if x == k: cnt += 1
for j in range(i - 1, -1, -1):
if nums[j] & x == nums[j]: break
if nums[j] == k: cnt -= 1
nums[j] &= x
if nums[j] == k: cnt += 1
ans += cnt
return ans