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. 末位数字等于 x。 这等价于：该子数组和对 10 取模的结果等于 x。

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

packagemainimport("fmt")funccountValidSubarrays(nums[]int,xint)(ansint){n:=len(nums)sum:=make([]int,n+1)fori,v:=rangenums{sum[i+1]=sum[i]+v}// 枚举子数组和的十进制长度forlow,high:=x,x+1;low<=sum[n];low,high=low*10,high*10{// 计算子数组和在 [low, high-1] 中，且子数组和模 10 为 x 的子数组个数cnt:=[10]int{}left1,left2:=0,0for_,s:=rangesum{// 随着 s 的增大，<= s-high 的前缀和离开窗口，<= s-low 的前缀和进入窗口forsum[left1]<=s-high{cnt[sum[left1]%10]--left1++}forsum[left2]<=s-low{cnt[sum[left2]%10]++left2++}ans+=cnt[(s-x+10)%10]}}return}funcmain(){nums:=[]int{1,100,1}x:=1result:=countValidSubarrays(nums,x)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defcount_valid_subarrays(nums,x):n=len(nums)pref=[0]*(n+1)fori,vinenumerate(nums):pref[i+1]=pref[i]+v ans=0low,high=x,x+1total=pref[-1]whilelow<=total:cnt=[0]*10left1=left2=0forsinpref:whilepref[left1]<=s-high:cnt[pref[left1]%10]-=1left1+=1whilepref[left2]<=s-low:cnt[pref[left2]%10]+=1left2+=1ans+=cnt[(s-x)%10]low*=10high*=10returnansif__name__=="__main__":nums=[1,100,1]x=1result=count_valid_subarrays(nums,x)print(result)

C++完整代码如下：

#include#includeusingnamespacestd;intcountValidSubarrays(constvector<int>&nums,intx){intn=nums.size();vector<longlong>sum(n+1,0);for(inti=0;i<n;i++){sum[i+1]=sum[i]+nums[i];}intans=0;// 枚举子数组和的十进制长度for(longlonglow=x,high=x+1;low<=sum[n];low*=10,high*=10){// 计算子数组和在 [low, high-1] 中，且子数组和模 10 为 x 的子数组个数intcnt[10]={0};intleft1=0,left2=0;for(longlongs: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];}}returnans;}intmain(){vector<int>nums={1,100,1};intx=1;intresult=countValidSubarrays(nums,x);cout<<result<<endl;return0;}