自己走过的坑希望大家也走一遍要不然太不公平这道题目正解是 dp 呦~： 这道题目不是 dp！是贪心呀 qwq
首先可以分析一下复杂度得到这道题目需要一个低于 O(n^2) 的算法。
首先学过小学都知道 3 \ | \ n 的判断条件是 3 \ | \ S(n) 其中 S(k) 表示 k 的数码和。
那么说出贪心思路：
- 若当前数字能被 3 整除，优先单独作为一个被 3 整除的数。
- 若当前余数和与之前某一位置的余数相同，且这两个位置之间没有前导零，那么这两个位置之间的子串能被 3 整除。
然后呢我们在便利的时候呢还需要记录 0,1,2 的最近位置，方便后续遍历。
我们暂且先用 l 数组记录 0,1,2 出现的最近位置，最开始初始化都为 -1 ， r 用来记录当前字串数码和模 3 的余数， res 用来记录答案。
我们遍历的时候需要这样更新：
- 若 d 能被 3 整除，将 r 加 1 ，重置 r 为 0 ，并更新 l 数组。
- 若 r 之前出现过，检查这两个位置之间是否有前导零。若没有前导零，将 res 加 1 ，重置 r 为 0 ，并更新 l 数组。
- 若 r 之前未出现过，更新 l_r 为当前位置 i 。
最后输出 res 即可。
代码就不放啦~都快说出来了！
复杂度：
- 时间复杂度： O(|s|) 其中 |s| 代表字符串 |s| 的长度。
- 空间复杂度： O(1) 没有额外开销。