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 1nums[0…1]sum 1 100 101nums[1…2]sum 100 1 101nums[2…2]sum 1因此答案为 4。题目来自力扣3969。大体步骤如下一、预处理前缀和先构造一个前缀和数组。前缀和数组的第 0 项为 0第 i 项表示原数组中前 i 个元素的总和。这样任意一个连续非空子数组的元素和都可以表示成两个前缀和相减。题目要求统计有效子数组数量就等价于统计有多少对前缀和它们的差值满足条件。二、拆解两个条件一个子数组的和要同时满足末位数字等于 x。这等价于该子数组和对 10 取模的结果等于 x。首位数字等于 x。一个正整数的首位数字等于 x意味着这个数落在若干个十进制区间中。具体来说对于每一个非负整数 k和必须落在从 x 乘以 10 的 k 次方到 (x1) 乘以 10 的 k 次方再减 1这个闭区间内。例如 x1 时区间依次是 [1,1]、[10,19]、[100,199]、[1000,1999] 等。三、外层枚举首位数字对应的区间从最小的情况开始令区间下界为 x上界为 x1。然后每次把下界和上界都乘以 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)。额外空间复杂度主要需要一个前缀和数组长度为 n1因此额外空间是 O(n)。滑动窗口中的计数数组长度固定为 10指针等变量都是常数个所以除前缀和数组外只用了 O(1) 的辅助空间。总额外空间复杂度为 O(n)。Go完整代码如下packagemainimport(fmt)funccountValidSubarrays(nums[]int,xint)(ansint){n:len(nums)sum:make([]int,n1)fori,v:rangenums{sum[i1]sum[i]v}// 枚举子数组和的十进制长度forlow,high:x,x1;lowsum[n];low,highlow*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}anscnt[(s-x10)%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):nlen(nums)pref[0]*(n1)fori,vinenumerate(nums):pref[i1]pref[i]v ans0low,highx,x1totalpref[-1]whilelowtotal:cnt[0]*10left1left20forsinpref:whilepref[left1]s-high:cnt[pref[left1]%10]-1left11whilepref[left2]s-low:cnt[pref[left2]%10]1left21anscnt[(s-x)%10]low*10high*10returnansif__name____main__:nums[1,100,1]x1resultcount_valid_subarrays(nums,x)print(result)C完整代码如下#includeiostream#includevectorusingnamespacestd;intcountValidSubarrays(constvectorintnums,intx){intnnums.size();vectorlonglongsum(n1,0);for(inti0;in;i){sum[i1]sum[i]nums[i];}intans0;// 枚举子数组和的十进制长度for(longlonglowx,highx1;lowsum[n];low*10,high*10){// 计算子数组和在 [low, high-1] 中且子数组和模 10 为 x 的子数组个数intcnt[10]{0};intleft10,left20;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;}anscnt[((s-x)%1010)%10];}}returnans;}intmain(){vectorintnums{1,100,1};intx1;intresultcountValidSubarrays(nums,x);coutresultendl;return0;}