2025-02-20：子数组按位与值为 K 的数目。用go语言，给定一个整数数组 nums 和一个整数 k，请计算满足条件的子数

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 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: &mutVec<i32>, k: i32) ->i64 {

  letmut ans: i64 = 0;

  letmut border = -1;

  letmut last_k = -1;

  foriin0..nums.len() {

      letx = nums[i];

      if x & k < k {

          border = i asi32;

          last_k = border;

          continue;

      }

      if x == k {

          last_k = i asi32;

      } else {

          letmut j = i asi32 - 1;

          while j > last_k {

              lety = nums[j asusize] & x;

              if y == k {

                  last_k = j;

                  break;

              }

              if y == nums[j asusize] {

                  break;

              }

              nums[j asusize] = y;

              j -= 1;

          }

      }

      ans += (last_k - border) asi64;

  }

  ans

}

fnmain() {

  letmut nums = vec![1, 1, 1];

  letk = 1;

  letresult = count_subarrays(&mut nums, k);

  println!("{}", result);

}

在这里插入图片描述Python完整代码如下：

# -*-coding:utf-8-*-

defcount_subarrays(nums, k):

  ans = 0

  border = -1

  last_k = -1

  for i, x inenumerate(nums):

      if (x & k) < k:

          border = i

          last_k = border

          continue

      if x == k:

          last_k = i

      else:

          for j inrange(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)

在这里插入图片描述引用链接