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

题目来自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 main

import "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 ans

if __name__ == "__main__":
    nums = [1, 1, 1]
    k = 1
    result = count_subarrays(nums, k)
    print(result)