注题解和代码有些来自 灵茶山艾府 大佬 和 力扣官方本人只是记录自己的刷题过程Day01 哈希1.两数之和创建一个哈希表对于每一个x我们首先查询哈希表中是否存在target - x然后将x插入到哈希表中即可保证不会让x和自己匹配。49.字母异位词分组由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。emplace_back128.最长连续序列本题是不能排序的因为排序的时间复杂度是 O(nlogn)不符合题目 O(n) 的要求。核心思路对于 nums 中的元素 x以 x 为起点不断查找下一个数 x1,x2,⋯ 是否在 nums 中并统计序列的长度。如果 x−1 在哈希集合中则不以 x 为起点。为什么因为以 x−1 为起点计算出的序列长度一定比以 x 为起点计算出的序列长度要长。设 m 为 nums 中的不同元素个数即哈希集合的大小。各个连续序列链是互相独立的如果我们发现其中一条链的长度至少为 m/2长度乘 2 大于等于 m由于不可能还有一条长度大于 m/2否则这两条链的长度之和就超过 m 了答案不会再增大此时可以直接返回答案。​Day02双指针283.移动零快慢指针快指针指向要交换的元素慢指针指向放元素的位置15.三数之和首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。移动left 和right 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。去重判断 nums[i] 与 nums[i 1]是否相同把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据当遍历到第一个-1 的时候判断 下一个也是-1那这组数据就pass了。要做的是 不能有重复的三元组但三元组内的元素是可以重复的。所以是判断 nums[i] 与 nums[i-1] 是否相同。11.盛最多水的容器容器的面积取决于短板移动长板永远不会得到更好的结果。因此在每一步我们都应该移动短板向内收缩。42.接雨水单调栈通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。就是用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。单调栈里只需要存放元素的下标i就可以。栈头到栈底的顺序如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。三个条件1.当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况。2.当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况。3.当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况。说回本题单调栈是按照行方向来计算雨水。从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。因为一旦发现添加的柱子高度大于栈头元素了此时就出现凹槽了栈头元素就是凹槽底部的柱子栈头第二个元素就是凹槽左边的柱子而添加的元素就是凹槽右边的柱子。遇到相同的元素更新栈内下标就是将栈里元素旧下标弹出将新元素新下标加入栈中。因为我们要求宽度的时候 如果遇到相同高度的柱子需要使用最右边的柱子来计算宽度。双指针对于任意一个位置i它能接多少雨水取决于它左边最高的墙和它右边最高的墙中较矮的那一个的高度。接水量 min(左边最高墙, 右边最高墙) - 当前柱子的高度如果算出来是负数即当前柱子比两侧最高的都高那它接不了水最多为 0。Day03滑动窗口3.无重复字符的最长字串维护一个动态的区间[left, right]即窗口使得这个窗口内的字符都是不重复的。right指针右边界 负责向右扩张试图把新的字符加入窗口。left指针左边界 负责在窗口出现重复字符时向右收缩直到去掉重复字符让窗口恢复“纯净”。438.找到字符串中所有字母的异位词在字符串s上维护一个长度为p.length()的固定大小窗口不使用两个哈希表分别统计p和窗口内的字符而是直接用一个大小为 26 的cnt数组。这个数组存储的是 “窗口内的字符需求余额”。滑动窗口总结1. 核心思想 “以空间换时间”滑动窗口的本质是在一个线性数据结构如数组、字符串上维护一个连续的区间子数组/子串。右指针 (right)负责扩张窗口引入新的元素。左指针 (left)负责收缩窗口在条件被破坏时移除旧元素。威力它把原本需要暴力枚举 O(N2)O(N2) 的子区间问题优化到了O(N)O(N) 的线性时间。因为每个元素最多被right访问一次被left访问一次。2. 适用场景什么时候用滑动窗口遇到以下特征通常优先考虑滑动窗口求最值求满足某个条件的最长或最短连续子数组/子串。特定条件子数组/子串的元素必须连续下标相邻。条件约束需要在满足某个业务条件如“无重复字符”、“包含目标字符串的所有字符”、“和不超过 K”的前提下进行查找。3. 灵魂分类固定窗口 VS 可变窗口滑动窗口通常分为两种类型模板略微不同A. 可变大小窗口最常见如“无重复字符的最长子串”窗口大小不是固定的。right不断右移一旦条件不满足就移动left直到条件重新满足然后比较长度。B. 固定大小窗口如“找到所有字母异位词”窗口长度固定为p.length()。right和left同时移动或者写两个循环先填满窗口再滑动。4. 核心难点与解决方案如何判断窗口内的状态简单场景求和直接用变量sum记录。复杂场景字符计数使用哈希表 (unordered_map)或固定大小数组 (int cnt[26])。特别是字母异位词那一题差额数组加进来减移出去加是非常精妙的优化。为什么有时要用while而不是if左指针收缩时可能收缩一次还不够。比如“异位词”里多了 2 个a你需要把left移动两次直到把多余的a完全踢出去。所以必须用while (条件)。边界条件小心数组越界。right s.size()是必须的。right - left 1是算长度的黄金公式注意区分下标差和实际长度下标差是right - left长度是right - left 1。