2026-07-13：统计好子数组。用go语言，给定一个整数数组 nums。对任意一个连续非空的子数组，考察它里面所有元素的按位或值（把该子数组

福大大架构师每日一题

发布于 2026-07-13 16:34:54

360

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

2026-07-13：统计好子数组。用go语言，给定一个整数数组 nums。

对任意一个连续非空的子数组，考察它里面所有元素的按位或值（把该子数组中每个元素依次做按位或，最终得到一个结果）。

如果这个按位或结果在该子数组中“至少出现过一次”（也就是子数组里存在某个元素的值，等于这个按位或结果），那么称这个子数组为“好子数组”。

请统计 nums 中所有好子数组的数量，并返回这个总数。

1 <= nums.length <= 100000。

0 <= nums[i] <= 1000000000。

输入： nums = [4,2,3]。

输出： 4。

解释：

nums 的子数组有：

子数组	按位或结果	存在于子数组中
[4]	4 = 4	是
[2]	2 = 2	是
[3]	3 = 3	是
[4, 2]	4 \| 2 = 6	否
[2, 3]	2 \| 3 = 3	是
[4, 2, 3]	4 \| 2 \| 3 = 7	否

因此，nums 的好子数组是 [4]、[2]、[3] 和 [2, 3]。所以答案为 4。

题目来自力扣3878。

大体步骤如下：

Go完整代码如下：

package main

import (
    "fmt"
)

func countGoodSubarrays(nums []int) (ans int64) {
    n := len(nums)
    left := make([]int, n)
    st := []int{-1} // 哨兵
    for i, x := range nums {
        forlen(st) > 1 && nums[st[len(st)-1]]|x == x {
            st = st[:len(st)-1]
        }
        left[i] = st[len(st)-1] // nums[left[i]] 不是 x 的子集
        st = append(st, i)
    }

    st = []int{n}
    for i := n - 1; i >= 0; i-- {
        x := nums[i]
        // 比如 nums = [...,1,...,1,...]，我们规定，包含左边的 1 的子数组，不能包含右边的 1，从而避免重复统计子数组
        // 注：包含右边的 1 的子数组，可以包含左边的 1
        forlen(st) > 1 && nums[st[len(st)-1]] != x && nums[st[len(st)-1]]|x == x {
            st = st[:len(st)-1]
        }
        right := st[len(st)-1] // nums[right] 不是 x 的子集
        st = append(st, i)

        // 子数组左端点可以从 left[i]+1 到 i，一共 i-left[i] 个
        // 子数组右端点可以从 i 到 right-1，一共 right-i 个
        ans += int64(i-left[i]) * int64(right-i)
    }

    return
}

func main() {
    nums := []int{4, 2, 3}
    result := countGoodSubarrays(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

def countGoodSubarrays(nums):
    n = len(nums)
    left = [0] * n
    st = [-1]  # 哨兵
    for i, x in enumerate(nums):
        while len(st) > 1 and (nums[st[-1]] | x) == x:
            st.pop()
        left[i] = st[-1]  # nums[left[i]] 不是 x 的子集
        st.append(i)

    ans = 0
    st = [n]
    for i in range(n - 1, -1, -1):
        x = nums[i]
        while len(st) > 1 and nums[st[-1]] != x and (nums[st[-1]] | x) == x:
            st.pop()
        right = st[-1]  # nums[right] 不是 x 的子集
        st.append(i)

        ans += (i - left[i]) * (right - i)

    return ans


if __name__ == "__main__":
    nums = [4, 2, 3]
    result = countGoodSubarrays(nums)
    print(result)

C++完整代码如下：

#include <vector>
#include <iostream>
using namespace std;

long long countGoodSubarrays(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n);
    vector<int> st;
    st.push_back(-1); // 哨兵
    for (int i = 0; i < n; ++i) {
        int x = nums[i];
        while (st.size() > 1 && (nums[st.back()] | x) == x) {
            st.pop_back();
        }
        left[i] = st.back(); // nums[left[i]] 不是 x 的子集
        st.push_back(i);
    }

    long long ans = 0;
    st.clear();
    st.push_back(n);
    for (int i = n - 1; i >= 0; --i) {
        int x = nums[i];
        // 比如 nums = [...,1,...,1,...]，我们规定，包含左边的 1 的子数组，不能包含右边的 1，从而避免重复统计子数组
        // 注：包含右边的 1 的子数组，可以包含左边的 1
        while (st.size() > 1 && nums[st.back()] != x && (nums[st.back()] | x) == x) {
            st.pop_back();
        }
        int right = st.back(); // nums[right] 不是 x 的子集
        st.push_back(i);

        // 子数组左端点可以从 left[i]+1 到 i，一共 i-left[i] 个
        // 子数组右端点可以从 i 到 right-1，一共 right-i 个
        ans += (long long)(i - left[i]) * (right - i);
    }
    return ans;
}

int main() {
    vector<int> nums = {4, 2, 3};
    long long result = countGoodSubarrays(nums);
    cout << result << endl;
    return0;
}