题目地址：

https://www.lintcode.com/problem/binary-stream/description

给定一个$0-1$字符串$s$（可能非常的长），找到所有其长为$k$的前缀$s[0:k-1]$的二进制数中是$3$的倍数的那些前缀，返回每个前缀的长度。以数组形式返回，并且由从小到大排序。

顺次计算出$s$前缀表示的数，如果是$3$的倍数就记下来。每次算完了直接转为除以$3$的余数继续计算。只需证明如果$n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}3)$，则$2n+x\equiv 2a+x(\mathrm{m}\mathrm{o}\mathrm{d}3)$，这是显然的。代码如下：

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { /** * @param s: the binary stream * @return: the outputs */ public int[] getOutput(String s) { // Write your code here int num = 0; List<Integer> list = new ArrayList<>(); for (int i = 0; i < s.length(); i++) { num = (num << 1) + s.charAt(i) - '0'; if (num % 3 == 0) { list.add(i + 1); } num %= 3; } int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }

时空复杂度$O(n)$。