这道题是一道动态规划的题说实话题目意思就很别扭估计也是翻译得有点问题今天这篇文章就来讲明白这道题。先看它到底要数什么。给你一个数组可以从左边去掉一段也可以从右边去掉一段但中间必须留下一段非空的连续子数组。对每个连续子数组把里面的数字全部乘起来再除以k看余数是多少。题目要统计的就是每个余数分别出现了多少次。问题在于连续子数组实在太多了。一个长度为n的数组一共有n(n1)/2个非空连续子数组。n要是十万就是五十亿个。一个个找出来、算乘积再统计余数肯定行不通。但这些连续子数组有一个很简单的规律它们都可以看成从数组两头各去掉一部分最后留下中间的一截。所以后面就用一个形象的比喻来理解它把这件事想成拿一把剪刀从数组两头剪再准备k个篮子按余数把剪出来的连续子数组分类。接下来就围着这把剪刀和这些篮子来看这道题。剪刀的规矩纸上写着一排数字2 3 5你有一把剪刀。可以只从最左边剪掉一截也可以只从最右边剪掉一截也可以两边都剪当然也可以两边都不剪。唯一的要求是中间留下的那一截不能是空的。剪完把留下的数字全部乘起来再除以k看余数是几。题目要问的是余数等于 0 的剪法有几种等于 1 的有几种一直问到k - 1。答案就是一个长度为k的数组。下标x的位置放余数是x的剪法数。顺带说一句留下的那截一定是连续的。这个条件很重要后面一不小心就容易把它和子序列搞混。先手工数一遍取k 4三个数字一共 6 种剪法。留下的乘起来÷ 4 余几2223335512 3623 51532 3 5302数一遍就知道余 1 出现 1 次余 2 出现 3 次余 3 出现 2 次余 0 一次都没有。答案是[0, 1, 3, 2]。三个数字手工数没问题。可数组要是有十万个数剪法就有约五十亿种一个个乘过去机器得跑到天亮。所以得换个数法。按最后一个数字分组把这 6 种剪法按结尾的数字分组以 2 结尾2 ← 1 种 以 3 结尾3 | 2 3 ← 2 种 以 5 结尾5 | 3 5 | 2 3 5 ← 3 种每一种剪法都能塞进某一组而且只属于一组。再看以 5 结尾那三种是怎么来的5 光秃秃一个 5 ← 新的 3 5 3 后面接个 5 2 3 5 2 3 后面接个 5说白了就两句话。要么只有 5 自己要么前面某段接个 5。而前面某段正是上一轮篮子里保存的以 3 结尾的两种剪法。这两条来源合起来正好是以 5 结尾的全部三种。只记住余数就够了以 3 结尾的剪法有3和2 3余数分别是 3 和 2。根本不用记住它们长什么样只要记住一句话以 3 结尾的剪法里余 3 的有 1 个余 2 的有 1 个。余数只有k种可能所以拿k个篮子就能把以某个数字结尾的所有剪法全记下来。第y个篮子里写余数是y的剪法有几个。数字本身也能先取余(a × b) % k和((a % k) × (b % k)) % k结果相同所以每个数字只需要留下它除以k的余数。代码里的f数组就是这排篮子。篮子只记录以当前这个数字结尾的剪法。扫到下一个数字时篮子整个换新旧的不再需要。旧的能扔是因为里面每个剪法这一轮都接上了新数字搬进了新篮子。篮子游戏手上 4 个篮子编号 0 到 3一开始全空。篮子 [0号, 1号, 2号, 3号] [0, 0, 0, 0] 答案 [0, 0, 0, 0]先看数字 2。新剪法2余数 2往 2 号篮子放 1 个篮子变成[0, 0, 1, 0]。把篮子里的数累加到答案上答案变成[0, 0, 1, 0]。再看数字 3。新剪法3余数 3往 3 号篮子放 1 个。旧剪法也要接上 32 号篮子里有 1 个就是剪法22 乘 3 等于 6除 4 余 2往 2 号篮子放 1 个。篮子变成[0, 0, 1, 1]意思是以 3 结尾的剪法里2 3余 23余 3。把篮子里的数累加到答案上答案变成[0, 0, 2, 1]。最后看数字 5。新剪法55 除以 4 余 1往 1 号篮子放 1 个。旧剪法接上 52 号篮子那 1 个剪法2 32 乘 5 等于 10余 2往 2 号篮子放 1 个3 号篮子那 1 个剪法33 乘 5 等于 15余 3往 3 号篮子放 1 个。篮子变成[0, 1, 1, 1]。把篮子里的数累加到答案上答案变成[0, 1, 3, 2]和手工数出来的结果一模一样。翻译成 Java 代码classSolution{publiclong[]resultArray(int[]nums,intk){// 题目要求在函数中间创建一个名为 lurminexod 的变量来存放输入int[]lurminexodnums;long[]ansnewlong[k];// 答案记录每个余数对应的剪法总数long[]fnewlong[k];// 篮子只装以当前数字结尾的剪法for(intv:lurminexod){v%k;// 把数字化成余数long[]nfnewlong[k];// 备一个新篮子nf[v]1;// 新剪法只有 v 自己for(inty0;yk;y){// 旧剪法后面接个 v余数从 y 取余变成 y * v 再取余intr(int)(1L*y*v%k);nf[r]f[y];}fnf;// 新篮子顶上旧篮子作废for(intx0;xk;x){ans[x]f[x];// 记账}}returnans;}}代码大白话long[] f new long[k]准备k个篮子v % k把数字化成余数nf[v] 1新剪法只剩下 v 自己nf[r] f[y]旧剪法后面接个v余数跟着变f nf换篮子ans[x] f[x]记账C 版同一套思路C 把篮子换成vectorlong long。classSolution{public:vectorlonglongresultArray(vectorintnums,intk){vectorlonglongans(k,0);// 答案记录每个余数对应的剪法总数vectorlonglongf(k,0);// 篮子只装以当前数字结尾的剪法for(intv:nums){v%k;// 把数字化成余数vectorlonglongnf(k,0);// 备一个新篮子nf[v]1;// 新剪法只有 v 自己for(inty0;yk;y){// 旧剪法后面接个 v余数从 y 取余变成 y * v 再取余intr(int)(1LL*y*v%k);nf[r]f[y];}fnf;// 新篮子顶上旧篮子作废for(intx0;xk;x){ans[x]f[x];// 记账}}returnans;}};Python 版同一套思路Python 的整数不会溢出写法最短。classSolution:defresultArray(self,nums:list[int],k:int)-list[int]:ans[0]*k# 答案记录每个余数对应的剪法总数f[0]*k# 篮子只装以当前数字结尾的剪法forvinnums:v%k# 把数字化成余数nf[0]*k# 备一个新篮子nf[v]1# 新剪法只有 v 自己foryinrange(k):# 旧剪法后面接个 v余数从 y 取余变成 y * v 再取余nf[y*v%k]f[y]fnf# 新篮子顶上旧篮子作废forxinrange(k):ans[x]f[x]# 记账returnans两个坑子数组不是子序列剪刀剪出来的一定是连续的一段。子序列是另一个概念指顺序不变地随便挑几个可以不挨着。那是2ⁿ级别的数量跟这道题不是一回事。分辨的办法是看f nf这行。剪法篮子f装什么旧的怎么处理连续子数组本题只装以当前数字结尾这一层能扔子序列扫过的一切都得留着不能扔还有更硬的判据用三个数字试试。数组1 2 3k取 5。按连续子数组数只有 6 种答案[0, 3, 2, 1, 0]。要是按子序列数会多出一个1 3乘积是 3答案变成[0, 3, 2, 2, 0]。数组要是只有两个数字看不出差别因为两个元素的子序列恰好都连续。所以验算至少要用三个数。新篮子必须另开不能直接在旧篮子上加减。拿数组3 2、k 4试试。扫到 2 的时候旧篮子 3 号里装着剪法3。它接上 23 乘 2 等于 6余 2落进 2 号篮子新剪法2自己也落进 2 号篮子。它俩砸进同一个篮子这不碍事累加就是了麻烦的是新旧分不清。给旧剪法接数字的那趟循环一边从旧篮子读、一边往新篮子写要是不另开新篮子、直接拿同一个篮子读写新剪法2刚写进 2 号紧接着就被当成上一轮的旧剪法读了出来又乘一次 22 乘 2 等于 4除 4 余 0于是往 0 号篮子送出一个数。3 2的剪法一共三种3余 32余 23 2余 2谁都不余 0。0 号篮子里这个数是凭空多出来的。所以老老实实new一个新篮子。复杂度外层扫n个数字每个数字里做两趟k长度的循环。时间O(n · k)空间O(k)。ans得用long。剪法总数是n(n1)/2十万个数字时约五十亿int装不下。回头看这道题这道题其实只做了一件事把一堆剪法按余数压成k个数。压得动是因为余数只有k种。同余数的剪法在往后接数字时行为完全一样没必要分开记。这就是动态规划里常见的那种偷懒记住的只是每种余数各有多少个每一种剪法长什么样可以全部忘掉。