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

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

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

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

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

1 <= nums.length <= 100000。

0 <= nums[i] <= 1000000000。

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

输出： 4。

解释：

nums 的子数组有：

子数组

按位或结果

存在于子数组中

4 = 4

2 = 2

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++完整代码如下：

  

  

using namespace std;

long long countGoodSubarrays(vector& nums) {
    int n = nums.size();
    vector left(n);
    vector 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 nums = {4, 2, 3};
    long long result = countGoodSubarrays(nums);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。