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

福大大架构师每日一题

发布于 2025-02-21 13:05:17

12000

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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)