什么是哈希1. 哈希表的核心思想哈希表内部其实是一个数组但它的特殊之处在于有一个哈希函数。当你存入一个键值对时哈希函数会根据键计算出一个整数哈希值然后把这个值映射到数组的某个位置下标把值存进去。当你想要根据键查找值时同样的哈希函数会再次计算出位置直接从数组里取出值速度非常快。例如你想把“张三”的成绩 95 分存起来。哈希函数可能把“张三”转换成数字 3那么就把 95 放到数组下标为 3 的位置。以后查“张三”时直接去下标 3 找立刻得到 95。2. 哈希表的基本操作插入计算键的哈希值 → 找到数组位置 → 存入值。查找计算键的哈希值 → 找到数组位置 → 取出值。删除同样计算位置然后把那个位置标记为空。这些操作在理想情况下时间复杂度都是O(1)也就是“常数时间”不管数据量多大速度几乎不变。3. 哈希冲突不同的键通过哈希函数可能会计算出相同的位置这叫“冲突”。比如“张三”和“李四”都映射到下标 3。解决冲突的常用方法有链地址法每个数组位置不直接存值而是存一个链表或红黑树。冲突时把新值挂在链表后面。开放地址法如果位置被占就按某种规则找下一个空位。优秀的哈希函数和合适的数组大小可以减少冲突保证效率。Q1两数之和方法一暴力枚举int n nums.length;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j] target) {return new int[]{i, j};}}}思路及算法两个指针一个慢指针i一个快指针ji1双重for循环外层控制慢指针内层控制快指针便利整个数组找到和我target的两个值返回其下标时间复杂度 ON方方法二哈希表使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。这样我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。时间复杂度ONMapInteger, Integer hashtable new HashMapInteger, Integer();for (int i 0; i nums.length; i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];Q2字母异位词分组方法排序什么是字母异位词两个单词如果包含的字母完全相同只是顺序不一样它们就是字母异位词。比如eat和tea都有 e、a、t 各一个顺序不同。listen和silent都有 l、i、s、t、e、n 各一个。分组的意思给你一堆单词比如[eat, tea, tan, ate, nat, bat]你要把它们分成小组每个小组里的单词都是字母异位词也就是长得不一样但字母组成相同。结果应该是第一组[eat, tea, ate]都由 e、a、t 组成第二组[tan, nat]都由 t、a、n 组成第三组[bat]由 b、a、t 组成独自一组怎么用哈希表分组这段话说的就是实现这个分组的思路找共同点标志同一组字母异位词有一个共同点比如把它们按字母顺序排序后会得到相同的字符串。eat排序后变成aettea排序后也变成aetate排序后也是aet所以aet就是这一组的“标志”。用哈希表存储哈希表就像一个字典键是上面说的标志比如aet值是一个列表存放所有属于这个标志的单词。遍历每个单词对于每个单词计算它的标志比如排序后的字符串。去哈希表里找这个标志如果已经有了就把当前单词加入对应的列表如果没有就新建一个列表把当前单词放进去然后以这个标志为键存入哈希表。最后结果遍历完所有单词后哈希表里每个键对应的值就是一个小组把这些值收集起来就是分组结果。举个实际例子用上面那组单词演示一开始哈希表是空的。遇到eat排序得aet哈希表里没有就新建一个列表[eat]以aet为键存入。遇到tea排序也得aet哈希表里有就把tea加到aet对应的列表里现在列表是[eat, tea]。遇到tan排序得ant哈希表里没有新建列表[tan]键为ant。遇到ate排序得aet找到对应列表加入变成[eat, tea, ate]。遇到nat排序得ant加入对应列表变成[tan, nat]。遇到bat排序得abt新建列表[bat]。最后哈希表里有三个键值对aet→[eat, tea, ate]ant→[tan, nat]abt→[bat]把这些列表拿出来就是分组结果。时间复杂度O(nklogk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串对于每个字符串需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表因此总时间复杂度是 O(nklogk)。空间复杂度O(nk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串Q3最长连续序列暴力法1. 暴力方法最直接的想法假设数组里有n个数我们可以挨个尝试对于每个数x看看x1在不在数组里如果在再看x2在不在……一直找到不能再延长为止。这样就能得到以x开头的最长连续序列。但这样每个数都要往后查最坏情况下每个数要查n次比如数组正好是1,2,3,...,n从 1 开始要查 n 次总时间就是 O(n²)太慢了。我们考虑枚举数组中的每个数 x考虑以其为起点不断尝试匹配 x1,x2,⋯ 是否存在假设最长匹配到了 xy那么以 x 为起点的最长连续序列即为 x,x1,x2,⋯,xy其长度为 y1我们不断枚举并更新答案即可。对于匹配的过程暴力的方法是 O(n) 遍历数组去看是否存在这个数2. 用哈希表提速我们注意到检查一个数在不在数组里如果用数组本身需要遍历很慢。但我们可以把所有数放进一个哈希表比如 HashSet这样检查一个数是否存在就只需要 O(1) 的时间瞬间完成。于是我们仍然遍历每个数但每次向后查找时用哈希表快速判断这样每个数向后查找的步骤虽然还是可能很多但至少查找本身快了。但是最坏情况仍然存在如果数组是[1,2,3,...,n]从 1 开始会查到 n从 2 开始也会查到 n……这样总次数还是 12...n ≈ n²/2仍然是 O(n²)。3. 关键优化避免重复查找为什么会有重复比如数组有连续序列[1,2,3,4]我们从 1 开始找到了 2,3,4得到了长度 4。然后我们继续从 2 开始又会找到 3,4但得到的长度只有 3比 4 短这个结果对我们求最大值没有意义。所以我们其实只需要从每个连续序列的起点开始找就能得到该序列的长度而中间的那些数有前驱的就不必再作为起点了。怎么判断一个数是不是序列的起点如果x-1不在数组中说明x前面没有连续的数那么x就是起点。如果x-1存在那x肯定不是起点因为可以从x-1开始得到更长的序列。所以我们在外层循环中只对那些没有前驱即x-1不存在的数进行向后查找。4. 时间复杂度分析外层循环要遍历每个数一共n次。但进入内层循环向后查找的只有那些没有前驱的数。每个没有前驱的数会向后找直到把整个连续序列走完。重要的是每个数只会被访问一次。因为如果一个数在某个连续序列里它要么是起点被外层循环选中然后向后找要么不是起点外层循环会跳过它但它在某个起点向后找时会被作为后续数访问到。所以所有数加起来内层循环的总次数就是n每个数最多被访问一次。因此总时间复杂度就是 O(n)。5. 举个例子数组[100, 4, 200, 1, 3, 2]放入哈希表。遍历每个数100检查99不存在所以是起点。向后找101不存在所以序列只有自己长度 1。4检查3存在吗存在因为数组有 3所以4不是起点跳过。200检查199不存在是起点。向后找201不存在长度 1。1检查0不存在是起点。向后找2存在继续找3存在继续找4存在继续找5不存在。得到序列1,2,3,4长度 4。3检查2存在不是起点跳过。2检查1存在不是起点跳过。最终得到最长长度 4。6. 为什么这样能保证每个数只被访问一次因为每个数要么是起点被外层循环选中后在内层循环中访问它自己以及后面的数要么不是起点外层循环会直接跳过但它在某个起点向后找时会被作为后续数访问到。并且每个数一旦被访问无论是作为起点还是作为后续就不会再被其他起点重复访问因为每个数只有一个前驱只能从一个起点出发到达。