2026-09-26：求和后首尾数字相同的有效子数组Ⅰ。用go语言，有一个整数数组 nums，还有一个目标数字 x。需要统计所有连续且非空的子数组

2026-09-26：求和后首尾数字相同的有效子数组Ⅰ。用go语言，有一个整数数组 nums，还有一个目标数字 x。需要统计所有连续且非空的子数组：先把子数组中的元素全部相加，得到总和；再看这个总和的十进制表示，如果最左边的数字和最右边的数字都等于 x，那么这个子数组就符合要求。最后返回符合要求的子数组总数。

1 <= nums.length <= 1500。

1 <= nums[i] <= 1000000000。

1 <= x <= 9。

输入： nums = [1,100,1], x = 1。

输出： 4。

解释：

有效子数组为：

nums[0..0]：sum = 1

nums[0..1]：sum = 1 + 100 = 101

nums[1..2]：sum = 100 + 1 = 101

nums[2..2]：sum = 1

因此，答案为 4。

题目来自力扣3969。

大体步骤如下：

一、预处理前缀和
先构造一个前缀和数组。前缀和数组的第 0 项为 0，第 i 项表示原数组中前 i 个元素的总和。这样，任意一个连续非空子数组的元素和，都可以表示成两个前缀和相减。题目要求统计有效子数组数量，就等价于统计有多少对前缀和，它们的差值满足条件。

二、拆解两个条件
一个子数组的和要同时满足：

1. 1. 末位数字等于 x。
   这等价于：该子数组和对 10 取模的结果等于 x。

2. 2. 首位数字等于 x。
   一个正整数的首位数字等于 x，意味着这个数落在若干个十进制区间中。具体来说，对于每一个非负整数 k，和必须落在：

• • 从 x 乘以 10 的 k 次方，

• • 到 (x+1) 乘以 10 的 k 次方再减 1
  这个闭区间内。
  例如 x=1 时，区间依次是 [1,1]、[10,19]、[100,199]、[1000,1999] 等。

三、外层枚举首位数字对应的区间
从最小的情况开始，令区间下界为 x，上界为 x+1。然后每次把下界和上界都乘以 10，得到下一个十进制长度对应的区间。只要下界不超过整个数组的总和，就说明还可能存在子数组和落在这个区间内，于是处理这个区间。处理完后继续扩大十倍，直到下界超过总和为止。

四、内层用滑动窗口统计每个区间内的有效子数组
对于当前枚举到的区间，需要统计有多少对前缀和满足：

• • 右端前缀和减去左端前缀和，结果落在当前区间内；

• • 这个差值对 10 取模等于 x。

具体做法是：依次把每一个前缀和当作右端前缀和。设当前右端前缀和为 s。那么左端前缀和 t 必须满足：

• • s 减去 t 的结果在当前区间内，也就是 t 要落在某个由 s 和当前区间边界共同决定的范围内；

• • t 对 10 取模的值，必须等于 s 减去 x 后对 10 取模的值。因为只有这样，s 减 t 的末位才会是 x。

由于原数组中的元素都是正整数，所以前缀和数组是严格递增的。对于不断增大的右端前缀和 s，满足数值范围条件的左端前缀和区间也会单调向右移动。因此可以用两个指针来维护这个窗口：

• • 一个指针负责把已经小于等于某个下界的前缀和移出窗口；

• • 另一个指针负责把小于等于某个上界的前缀和加入窗口。

同时用一个长度为 10 的计数数组，记录当前窗口内各个前缀和模 10 的出现次数。每处理一个右端前缀和 s，就查询计数数组中模 10 等于目标值的次数，这个次数就是以 s 为右端、满足当前区间和末位条件的有效左端前缀和数量。把它累加到答案中。

五、重复处理所有区间
对每一个由首位数字条件产生的区间，都重新执行一次上述滑动窗口统计。不同区间之间互不影响，最后把所有区间统计到的数量相加，就是最终有效子数组的总数。

六、为什么不会统计到空子数组
因为原数组元素都为正数，前缀和严格递增。对于当前右端前缀和 s，窗口中加入的左端前缀和一定小于 s，所以对应的子数组长度至少为 1，不会出现空子数组。

七、复杂度分析
时间复杂度：外层枚举的区间数量大约是所有元素总和的对数级别，即 O(log10(总和)) 次。内层每个区间都要遍历所有前缀和一次，并且两个指针各自单调移动，总移动次数与前缀和数量同阶。因此每个区间的时间是 O(n)。总时间复杂度为 O(n × log10(总和))。由于总和最大约为 1500 × 10^9，对数很小，实际接近 O(n)。
额外空间复杂度：主要需要一个前缀和数组，长度为 n+1，因此额外空间是 O(n)。滑动窗口中的计数数组长度固定为 10，指针等变量都是常数个，所以除前缀和数组外只用了 O(1) 的辅助空间。总额外空间复杂度为 O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func countValidSubarrays(nums []int, x int) (ans int) {
    n := len(nums)
    sum := make([]int, n+1)
    for i, v := range nums {
        sum[i+1] = sum[i] + v
    }

     // 枚举子数组和的十进制长度
    for low, high := x, x+1; low <= sum[n]; low, high = low*10, high*10 {
        // 计算子数组和在 [low, high-1] 中，且子数组和模 10 为 x 的子数组个数
        cnt := [10]int{}
        left1, left2 := 0, 0
        for _, s := range sum {
            // 随着 s 的增大，<= s-high 的前缀和离开窗口，<= s-low 的前缀和进入窗口
            for sum[left1] <= s-high {
                cnt[sum[left1]%10]--
                left1++
            }
            for sum[left2] <= s-low {
                cnt[sum[left2]%10]++
                left2++
            }
            ans += cnt[(s-x+10)%10]
        }
    }
    return
}

 func main() {
    nums := []int{1, 100, 1}
    x := 1
    result := countValidSubarrays(nums, x)
    fmt.Println(result)
}

Python完整代码如下：

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

 def count_valid_subarrays(nums, x):
    n = len(nums)
    pref = [0] * (n + 1)
    for i, v in enumerate(nums):
        pref[i + 1] = pref[i] + v

     ans = 0
    low, high = x, x + 1
    total = pref[-1]

     while low <= total:
        cnt = [0] * 10
        left1 = left2 = 0

         for s in pref:
            while pref[left1] <= s - high:
                cnt[pref[left1] % 10] -= 1
                left1 += 1

             while pref[left2] <= s - low:
                cnt[pref[left2] % 10] += 1
                left2 += 1

             ans += cnt[(s - x) % 10]

         low *= 10
        high *= 10

     return ans

 if __name__ == "__main__":
    nums = [1, 100, 1]
    x = 1
    result = count_valid_subarrays(nums, x)
    print(result)

C++完整代码如下：

  

  

using namespace std;

 int countValidSubarrays(const vector& nums, int x) {
    int n = nums.size();
    vector 
 
 sum(n +  
 1, 0);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }

     int ans = 0;

     // 枚举子数组和的十进制长度
    for (long long low = x, high = x + 1; low <= sum[n]; low *= 10, high *= 10) {
        // 计算子数组和在 [low, high-1] 中，且子数组和模 10 为 x 的子数组个数
        int cnt[10] = {0};
        int left1 = 0, left2 = 0;

         for (long long s : sum) {
            // 随着 s 的增大，<= s-high 的前缀和离开窗口，<= s-low 的前缀和进入窗口
            while (sum[left1] <= s - high) {
                cnt[sum[left1] % 10]--;
                left1++;
            }
            while (sum[left2] <= s - low) {
                cnt[sum[left2] % 10]++;
                left2++;
            }
            ans += cnt[((s - x) % 10 + 10) % 10];
        }
    }

     return ans;
}

 int main() {
    vector nums = {1, 100, 1};
    int x = 1;
    int result = countValidSubarrays(nums, x);
    cout << result << endl;
    return0;
}

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