最近刷题的时候碰到一个挺有意思的字符串处理问题题面很简短翻译成人话大概是这样的给你一个只包含数字的字符串然后来一堆区间查询每次给你一个区间 [l, r]你要在这个子串里把所有“非零”的字符数字按从左到右的顺序挑出来、拼成一个数再把这些非零数字的数值和算出来最后把这两个东西乘起来作为答案。说实话第一眼看上去感觉就是个模拟题但仔细一琢磨“每个查询区间”这几个字一出来事情就没那么简单了。如果直接每个查询都去扫描一遍子串那复杂度轻松爆炸尤其是字符串长度和查询次数都到十万级别的时候。今天的主题就是用 Go 语言把这个题做得漂亮核心思路是前缀和 幂次预处理把每次查询压到 O(1)顺便把大数乘法和溢出这些暗坑也一起处理干净。这个题非常适合拿来练 Go 的数组操作和数学推导对刚学完 go语言基础、想进阶的同学来说是一道性价比很高的综合题。下面我从题意拆解、数学推导到完整代码实现把整条链路捋一遍。1. 先搞清楚题目到底在问什么很多同学看到“连接非零数字并乘以其数字和”这种题面第一反应是懵的。我们先把这个规则拆干净确保每一步都明确。1.1 “连接非零数字”和“数字和”分别是什么给定一个字符串 s 1203405假设查询区间是 [1, 5]这里我按 1-based 下标后面实现里也统一用这个约定子串就是 12034。第一步按从左到右的顺序把所有非零的字符数字拿出来字符 1 - 数字 1字符 2 - 数字 2字符 0 是零跳过字符 3 - 数字 3字符 4 - 数字 4于是得到数字序列 [1, 2, 3, 4]按顺序拼接成一个整数就是 1234。第二步算这些非零数字的“数字和”也就是 1 2 3 4 10。这里要特别提醒一下“数字和”不是让你把拼接出来的 1234 的每一位再拆开求和——虽然在这个特定问题里这两种理解恰好等价因为拼接出来的数本来就只包含这些非零数字每一位就是那些非零数字本身。但从题目设计的角度理解更准确的说法是对所有挑出来的非零数字字符做一个数值累加。这个细节在后面设计前缀数组的时候很关键。最终答案就是 1234 × 10 12340。如果区间里全是零比如子串是 000那就没有任何非零数字拼接结果为空这时候答案应该输出 0这个边界要单独处理后面我会讲。1.2 为什么不能直接暴力扫描每个区间最朴素的做法每次查询都从 l 遍历到 r把非零数字拼接、求和、相乘复杂度是 O(区间长度)。如果字符串长度 n 是 10^5查询次数 q 也是 10^5最坏情况下总操作量是 10^10 量级在 Go 里哪怕常数再小也是铁定超时的。所以问题的本质是一个典型的“区间聚合查询”问题我们被反复询问某个区间的一些统计信息这些信息有某种可减性或者可以通过其他信息还原出来。最经典的思路就是前缀和。这里存在一个障碍拼接操作不像普通加法那样直观。假设我已经算出了前缀的拼接值比如前 5 个非零数字拼成了 123现在又来一个数字 4拼接结果应该是 123 × 10 4 1234。这个操作本身很简单但区间查询时不能直接拿两个前缀值相减因为拼接数不是简单的累加量它跟“区间内非零数字的个数”有关。这个问题就需要一点数学推导来解决了。2. 核心思路用三个前缀数组搞定一切要把查询复杂度压到 O(1)关键在于设计好预处理阶段的信息。这个题我最终用了三个数组非零数字计数前缀数组、非零数字数值和前缀数组、非零数字拼接值前缀数组外加一个 10 的幂次数组。下面一个一个说清楚。2.1 计数前缀和与数字和前缀第一个数组 cntcnt[i] 表示原字符串前 i 个字符我习惯用 1-based 语义cnt[0] 0中非零数字的个数。第二个数组 sumsum[i] 表示前 i 个字符中所有非零数字的数值之和。这两个数组用脚趾头都能想明白遍历一遍字符串就能构建遇到字符 0cnt 和 sum 都不变遇到非零字符 ccnt[i] cnt[i-1] 1sum[i] sum[i-1] int(c - 0)。区间查询的时候区间 [l, r] 内的非零数字个数 c cnt[r] - cnt[l-1]数字和 segSum sum[r] - sum[l-1]。这两个信息已经能回答“数字和”这一半了。2.2 拼接值的区间还原一个漂亮的数学公式麻烦的是“拼接值”。如果有一个数组 valval[i] 表示“前 i 个字符中的所有非零数字按顺序拼接成的整数”那我怎么从 val[r] 和 val[l-1] 还原出区间 [l, r] 的拼接值先看一个事实val[r] 本质上是“所有非零数字拼接出来的一个完整整数”。假设前缀 l-1 的部分拼接成了 X区间 [l, r] 内的非零数字拼接成了 YY 一共有 c 位c 恰好就是区间内非零数字的个数那么整个前缀 r 的拼接值就是val[r] X × 10^c Y这个式子非常好理解随便举个数前缀拼接值是 12区间内拼接值是 345c 3整个值就是 12 × 1000 345 12345。所以反过来Y val[r] - val[l-1] × 10^c用这个公式只要预处理了 val 数组和 10 的幂次数组 pow10每次查询就能 O(1) 还原区间拼接值。这里再强调一个容易忽略的细节指数 c 不是区间长度而是区间内“非零数字的个数”。因为拼接过程会跳过零零不产生新的数字位所以在乘 10 的幂次时补位的数量必须跟非零数字的数量严格一致否则公式就错了。2.3 取模的必要性与 pow10 数组的构建标题里的“Ⅱ”说明这是一个系列题通常这种题的输出会涉及一个很大的整数因为非零数字拼接出来可能长达 10^5 位这在任何固定位数的整数类型里都存不下。所以常见的赛题版本会要求对结果取模比如模 10^97。这个题目的描述里虽然没有明确写模数但工程上比较稳妥的做法是默认处理取模版本同时在文章最后给大家补充不取模时该怎么做。我用的模数 mod 1000000007这是一个经典的质数模数Go 的 int64 完全装得下中间运算结果。pow10 数组的含义是 10 的 i 次方对 mod 取模的结果。构建时一个循环搞定pow10 : make([]int64, n1) pow10[0] 1 for i : 1; i n; i { pow10[i] pow10[i-1] * 10 % mod }为什么只需要准备到 n因为区间内非零数字个数最多也就是整个字符串的长度 n所以幂次最大就是 n。2.4 为什么这套方案能跑得快整体的时间复杂度分两部分预处理阶段遍历一次字符串 O(n)查询阶段每个区间进行常数次加减乘和取模O(1)。所以总复杂度是 O(n q)即使 n 和 q 都是 10^6 级别也能轻松跑完。空间上用了 4 个长度为 n1 的 int64 数组大约 4 × 8 × 10^5 3.2MB在 Go 的内存模型下毫无压力。对比一下暴力做法的 O(nq)这个优化力度是数量级的飞跃也是这个题最核心的价值所在让你意识到“区间查询”类问题永远先去想能不能用前缀信息表达出来。3. Go语言完整实现与逐段拆解光讲理论不行代码也得能直接抄。下面我给出一份完整的 Go 实现并标好注释方便对照理解。3.1 核心代码预处理 查询package main import ( bufio fmt os ) const mod 1000000007 func main() { in : bufio.NewReader(os.Stdin) out : bufio.NewWriter(os.Stdout) defer out.Flush() var n, q int fmt.Fscan(in, n, q) var s string fmt.Fscan(in, s) cnt : make([]int, n1) // 非零数字个数前缀 sum : make([]int64, n1) // 非零数字数值和前缀 val : make([]int64, n1) // 非零数字拼接值前缀取模 pow10 : make([]int64, n1) // 10的幂次取模 pow10[0] 1 for i : 0; i n; i { cnt[i1] cnt[i] sum[i1] sum[i] val[i1] val[i] pow10[i1] pow10[i] * 10 % mod if s[i] ! 0 { d : int64(s[i] - 0) cnt[i1] sum[i1] d val[i1] (val[i]*10 d) % mod } } for i : 0; i q; i { var l, r int fmt.Fscan(in, l, r) c : cnt[r] - cnt[l-1] if c 0 { fmt.Fprintln(out, 0) continue } segVal : (val[r] - val[l-1]*pow10[c]%mod mod) % mod segSum : sum[r] - sum[l-1] ans : segVal * (segSum % mod) % mod fmt.Fprintln(out, ans) } }3.2 关键代码逻辑说明预处理循环里我用了“先继承后更新”的模式cnt、sum、val 每个新位置都先等于前一个位置的值然后根据当前字符是否为零决定要不要更新。这样做的原因是保持前缀定义的完整性如果当前字符是零那么前 i1 个字符的非零数字集合跟前 i 个字符是完全一样的值必须继承下来。val 的更新使用了拼接公式把当前数字 d 追加到已有拼接值的末尾等价于 val[i] × 10 d。在取模的情况下因为 (a×10 d) mod M (a mod M × 10 d) mod M所以每一步取模是安全的。查询阶段里segVal : (val[r] - val[l-1]*pow10[c]%mod mod) % mod这行要仔细看。val[l-1] × pow10[c] 本身可能已经很大所以先取了 mod再用 val[r] 去减。减完之后可能是负数所以加一个 mod 再取一次模保证结果是 [0, mod) 范围内的非负整数。这是 Go 里处理负数取模的标准写法千万别省掉中间那个 mod。segSum 是 int64 类型理论上最大值是 n × 9n 到 10^6 也只有 9×10^6远不会溢出所以直接算就行。最后乘之前再对 segSum 取一次模避免出现更大的中间结果。3.3 输入输出与性能细节字符串长度和查询次数都很大时fmt.Fscan 和 fmt.Fprintln 配合 bufio.Reader 和 bufio.Writer 已经足够应对不需要再手动写快读。这里有几个性能小习惯尽量把输出 writer 攒到最后统一 flush减少系统调用次数如果输入里只有数字和空格可以尝试用 strings.Fields 一次读完但 bufio.Fscan 的通用性更好代码也更简洁在极大规模比如 n, q 到 10^7下可以换用自定义的 readInt 函数但对于绝大多数练习场景上面的写法足够了。4. 实战踩坑我从这个题里学到的几个教训这个题表面简单实际代码一写各种问题就冒出来了。我把在本地测试和提交时踩过的坑整理一下每一条都是真金白银换来的。4.1 索引从 0 到 1 的偏移最容易犯错Go 的字符串下标天然是 0-based而题目查询输入通常是 1-based。我在前缀数组里把下标 i 定义为“前 i 个字符”也就是 index 0 表示空前缀index i 对应 s[0..i-1]。这样查询 [l, r] 时区间内字符对应的前缀下标分别是 l-1 和 r。这个设计在很多题里都很管用但代价是容易把边界搞混。我调试时遇到过一次查询 [1, 1] 结果不对最后发现是在初始化循环里写成了 cnt[i] cnt[i-1]导致 cnt[0] 被赋了垃圾值。正确写法是循环变量 i 从 0 到 n-1新位置统一用 i1。建议拿到任何一道区间题先把“我的数组下标代表什么”写在注释里再开始写循环别省这几秒。4.2 全零区间不是“正常跑公式”能 cover 的如果区间内没有非零数字c 0val[l-1] × pow10[0] val[l-1]segVal val[r] - val[l-1]。如果 l-1 和 r 之间恰好没有任何非零数字val[r] 就等于 val[l-1]segVal 计算结果为 0看似没问题。但等一下真的没问题吗如果字符串是 0001000查询 [5, 7]子串是 000非零数字个数确实是0公式算出 segVal 0。可如果查询区间跨过一个非零数字但区间本身为零呢比如查询 [2, 3]子串 00val[3] 可能包含前面某个非零数字val[1] 也可能包含那个非零数字两者相等结果还是 0。这个公式在数学上其实是自洽的但问题在于 c 0 时segSum 一定也是 0最终结果注定是 0。为了避免不必要的计算和潜在的边界混淆我在代码里显式判断了 c 0直接输出 0。这个分支看起来多余实际上能让逻辑更清晰也能防止某些变体题里对空拼接值的特殊定义造成混淆。4.3 取模时机不对结果悄悄出错我第一次写的时候segVal 直接这样写segVal : (val[r] - val[l-1]*pow10[c] mod) % mod忽略了 pow10[c] 和 val[l-1] 都是模过 M 的数它们相乘以后可能超过 int64 的安全范围吗两个 int64 数相乘最大可以达到 (10^9)^2 10^18int64 的上限是约 9.2×10^18看起来不溢出。但如果模数不是 10^97而是更大的值或者以后题目变了这里很容易炸。正确的做法是先对乘积取模segVal : (val[r] - val[l-1]*pow10[c]%mod mod) % mod这里有个优先级要提醒在 Go 里% 和 *、/ 是同一优先级从左到右结合。所以 val[l-1]*pow10[c]%mod 会先算 val[l-1] * pow10[c]再整体对 mod 取模这正是我想要的效果不会产生歧义。4.4 val 的拼接值取模后会丢信息吗有同学可能会担心val 是取模后的拼接值用它去还原 segVal结果还是“真实的拼接值”吗答案是在模 M 的意义下是。因为整个公式里只有加减和乘法这些运算在模运算下是同态映射——对每个数先取模再运算和先运算再取模结果一致。所以 val[r] 和 val[l-1] 都取模后segVal 得到的是真实区间拼接值对 M 取模的结果这正好是题目要求的答案。如果你真的遇到了不取模的题目那情况下面的 big.Int 方案会更合适但复杂度会明显变高后面第五节单独讲。4.5 本地测试时用对拍验证提交前我习惯写一个暴力解法做对拍。小数据量下随机生成字符串和查询区间比较每个查询的暴力结果和优化版本结果。对拍代码逻辑很简单暴力函数直接对 s[l:r] 遍历维护一个 int64 的拼接值和一个 int64 的和最后相乘。因为小数据不会溢出所以能直接算。如果对拍十万组随机数据全都一致我才会提交。这个习惯帮我抓到了不止一个因为索引偏移导致的隐蔽 bug强烈推荐。5. 延伸思考与进一步的优化空间接下来聊几个跟这个题相关的进阶话题也是我在做完之后自己思考过的问题分享出来给大家一些启发。5.1 不取模时怎么办big.Int 与性能取舍如果题目明确要求输出完整的大整数不取模那情况就复杂了。区间拼接值可能是一个十万位的十进制整数Go 内置的 int64 完全装不下这时候必须使用 math/big 包。思路依然是前缀和只不过 val 数组不能存 int64 了得存 *big.Int。问题是这样一来内存和时间都会翻倍而且每次区间查询如果要构造完整的大数复杂度容易退化。一种可行的方案是不是每个位置都存完整前缀大数而是存一个结构体包含拼接值对应的 big.Int查询时通过减法得到区间的拼接值再与数字和相乘。但这种实现的常数非常大实测在 n, q 都为 10^5 时运行时间可能比取模版本慢一个数量级甚至更多。所以竞赛题里基本不会这么出如果真遇到了大概率是 n 和 q 都不大或者要求用十进制字符串处理。从这里也能看出出题人让你取模不只是为了刁难你更是在给你降低难度。5.2 如果查询区间很大还能更快吗目前的 O(n q) 已经是最优渐进复杂度了因为你至少要把字符串读一遍、把每个查询读一遍。常数方面还有一点优化空间pow10 数组可以只在需要时用快速幂计算但这样每个查询变成 O(log n)反而更慢所以预处理所有幂次是更合适的选择。内存方面cnt 数组理论上可以用 int32 甚至 int16但在 Go 里这些类型的运算需要额外转换反而可能变慢所以直接用 int 就好不必过度优化。5.3 这类“跳过特定字符再拼接”的题目还有什么变体我做完这个题第一反应是联想到“去除某些字符后求哈希值”一类的问题。比如给你一个字符串查询区间内去掉空格后拼接起来的哈希值或者去掉元音字母后拼接起来再取模。核心思想完全一致维护一个“有效字符计数前缀”维护一个“聚合值前缀”查询时用 cnt 差作为幂次或长度修正。掌握了这个套路遇到类似题目基本能秒出思路。关键在于识别出问题中的“跳过规则”是否只影响字符的选择不影响相对顺序。只要相对顺序保持就可以用类似的前缀拼接公式。5.4 用这个题强化 Go 的切片思维说实话这个题也是一道很好的 Go 练习题。它强迫你思考下标语义、切片边界、数组复用这些都是 go语言基础 里比较容易薄弱的地方。我在给新手做代码 review 时经常发现很多同学写循环喜欢复制粘贴、i 和 i1 混用这个题就是治这个毛病的好药。建议拿到代码后手动跑几个小样例把 cnt、sum、val、pow10 四个数组的每个下标都手算一遍画一张表出来去对比。这个过程看着笨但对理解和记忆是非常扎实的。6. 本地测试用例与最终验证最后放一组我用的测试数据大家可以拿去直接跑一下验证自己的实现是否正确。输入7 4 1203405 1 5 2 3 1 7 4 6输出期望12340 4 26010 420我手算其中两个验证一下查询 [2, 3]子串是 20非零数字只有 2拼接值 2数字和 2答案 4。查询 [4, 6]子串是 340非零数字是 3 和 4拼接值 34数字和 7答案 238等等这里我重新算一下s[4] 3s[5] 4s[6] 0子串是 340拼接值是 34数字和是 3 4 734 × 7 238不是 420。看来上面期望值写错了我纠正一下实际应该输出[1, 5]1234 × 10 12340[2, 3]2 × 2 4[1, 7]12345 × 15 185175[4, 6]34 × 7 238所以真正的期望输出是12340 4 185175 238这个小插曲其实也说明了一个问题手算期望值很容易出错尤其是指定多个区间的时候。所以我在本地总是跑对拍而不是依赖手算这一点值得所有人养成习惯。我自己在实现完后用随机生成的数据跑了十万组对拍结果完全一致才最终定稿。整个过程下来最大的感受是这个题的核心难点不在 Go 语法而在你能不能看穿“前缀拼接值”背后的数学本质。只要理解了 val[r] val[l-1] × 10^c intervalVal 这个公式整个题目就豁然开朗了。最后再分享一个小技巧调试这种带前缀数组的题目别急着用 fmt.Println 打印整个数组。如果你只打印某个区间相关的几个值信息噪音会小很多问题定位反而更快。我就是靠这种方式把一开始那个隐蔽的取模负数问题揪出来的。希望这篇文章能帮你在 Go 的算法路上少踩几个坑咱们下次见。