...

1. 记录出现次数或出现位置（哈希表可以看成是O(1)复杂度）
2. 查表法（打表）

数组

1. 前缀和
2. 双指针
3. map<int, int> count;

关于数组的数量级，一些比较微妙的点如下：

1. num[i] <= 10^9，如果不涉及求和，则可以用int表示，如果涉及求和，则只能用long long
2. num[i] <= 10^5，k <= 10^5，k表示数组成员个数，这里如果涉及求和，则结果就是刚好int溢出，所以只能用long long。

字符串

1. 分隔字符串
2. 统计单词数
3. 回文

除前缀后，后缀后也是可以用的，比如：https://leetcode-cn.com/problems/shifting-letters/