2025-02-20：子数组按位与值为 K 的数目。用go语言，给定一个整数数组 nums 和一个整数 k，请计算满足条件的子数组数量：这些子数组的所有元素经过按位与运算后的结果等于 k。

1 <= nums.length <= 100000。

0 <= nums[i], k <= 1000000000。

输入：nums = [1,1,1], k = 1。

输出：6。

解释：

所有子数组都只含有元素 1 。

答案2025-02-20：

chatgpt[1]

题目来自leetcode3209。

大体步骤如下：

1.初始化变量 ans 为 0，border 和 lastK 均为 -1，用于记录边界和上一次遇到 k 的位置。

2.对于输入的数组 nums 中的每个元素，遍历其索引 i 和元素 x：

2.1.如果 x 与 k 的按位与结果小于 k，则更新 border 和 lastK 为当前索引 i，表示单独的元素满足条件。

2.2.如果 x 等于 k，则更新 lastK 为当前索引 i。

2.3.如果 x 大于 k，则从 i-1 开始逆向遍历到上次遇到 k 的位置之间的元素：

2.3.1.计算 nums[j] 和 x 的按位与结果为 y。

2.3.2.若 y 等于 k，则更新 lastK 为 j，并结束当前循环。

2.3.3.若 y 等于 nums[j]，表示按位与后的结果没有改变，直接结束当前循环。

2.3.4.否则，更新 nums[j] 为 y。

3.在每次迭代中，累加符合条件的子数组数量，即 lastK - border。

4.返回最终的 ans 作为结果。

总的时间复杂度：O(n)，其中 n 为数组 nums 的长度。

总的额外空间复杂度：O(1)，除了几个整型变量外，没有使用额外的空间。

Go完整代码如下：package mainimport "fmt"func countSubarrays(nums []int, k int) int64 { ans := int64(0) border, lastK := -1, -1 for i, x := range nums { if x&k < k { border = i lastK = border continue } if x == k { lastK = i } else { for j := i - 1; j > lastK; j-- { y := nums[j] & x if y == k { lastK = j break } if y == nums[j] { break } nums[j] = y } } ans += int64(lastK - border) } return ans}func main() { nums := []int{1, 1, 1} k := 1 result := countSubarrays(nums, k) fmt.Println(result)}

在这里插入图片描述

Rust完整代码如下：fn count_subarrays(nums: &mut Vec<i32>, k: i32) -> i64 { let mut ans: i64 = 0; let mut border = -1; let mut last_k = -1; for i in 0..nums.len() { let x = nums[i]; if x & k < k { border = i as i32; last_k = border; continue; } if x == k { last_k = i as i32; } else { let mut j = i as i32 - 1; while j > last_k { let y = nums[j as usize] & x; if y == k { last_k = j; break; } if y == nums[j as usize] { break; } nums[j as usize] = y; j -= 1; } } ans += (last_k - border) as i64; } ans}fn main() { let mut nums = vec![1, 1, 1]; let k = 1; let result = count_subarrays(&mut nums, k); println!("{}", result);}

在这里插入图片描述

Python完整代码如下：# -*-coding:utf-8-*-def count_subarrays(nums, k): ans = 0 border = -1 last_k = -1 for i, x in enumerate(nums): if (x & k) < k: border = i last_k = border continue if x == k: last_k = i else: for j in range(i - 1, last_k, -1): y = nums[j] & x if y == k: last_k = j break if y == nums[j]: break nums[j] = y ans += last_k - border return ansif __name__ == "__main__": nums = [1, 1, 1] k = 1 result = count_subarrays(nums, k) print(result)

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP