一.哈希1.两数之和思路数组中两数之和为target——num和target-num均位于该数组中步骤构建空哈希表将nums存入哈希表中当target - nums存在于哈希表中时即找到两数之和为target的组合49.字母异位词分组思路对于每个字符串其有序形态作为字典的key对应的value为存有原字符串的数组。步骤字符串拆分排序sort拼接后得到有序字符串.join(sort(a))有序字符串作为字典的key构造空数组作为value。遍历原字符串其有序字符串在key中时将其加入key对应的value数组其有序字符串不在key中时将有序字符串-空数组构造成新的key-value对最后输出list(a.values())128.最长连续序列思路未排序数组O(n)级别的时间复杂度——排序的时间复杂度最低都是O(nlogn)判断某个数是否有相邻数——1之后的数是否在原数组中即可1的次数即为连续序列的长度但如果遍历每个数组的数进行判断会极大增加时间复杂度对每个数先进行-1判断-1之后仍在原数组中说明原数不是序列的最小数则直接跳过步骤先将数组转化为集合set一可以去重二可以降低查找复杂度为O(1)遍历每个数进行-1判断-1之后仍在原数组中说明原数不是序列的最小数则直接跳过若是最小数则进行1判断注意序列长度为1次数再1二.双指针283.移动零思路错误思路左侧指针遍历右侧指针记录零区域的左边界当左侧遍历遇到0时通过两两交换将0换到最右侧。这种思路的最大隐患在于如果遇到连续0就会将后置位的0换到本位然后左指针右移就会跳过对移动到本位的0的判断和处理正确思路一个指针用于遍历一个指针用于记录非零数量非零数前移即可步骤i指针遍历数组j指针记录非零数个数当遇到非零数就把它的值赋给第j位数遍历结束后第j1到第n的数全部赋值为0即可11.盛最多水的容器思路面积计算为s min(height[i],height[j])*[j-i]本质上是遍历i,j寻找s的最大值错误思路双for循环固定i遍历j然后移动i再遍历j这样计算量就一定是O(n)正确思路当确定i,j之后面积其实是被height[i],height[j]中的最小者决定的改变更大者的值是不可能让面积增大的所以双指针分别从左和右向中间移动从而大大减少计算量步骤i从0出发j从n-1出发while循环条件为ij内部为先计算s min(height[i],height[j])*[j-i]并与max_s进行比较然后比较height[i],height[j]的大小移动二者中最小者的指针。15.三数之和思路错误思路1三重循环遍历nums[i] nums[j] nums[k] 0最后对所有的三元组进行去重检查思路排序双指针或者排序哈希表对有序数组求三数之和从左往右遍历固定nums[i]后考虑两种特殊情况1.nums[i]0此时三数之和不可能为0直接break2.i 2且nums[i]nums[i-1]此时说明遍历的这个数和前面的数是重复的则直接continue跳过除这两种特殊情况外在i右侧数组两端选取左右双指针l,r通过while(lr)进行循环判断nums[i] nums[l] nums[r]是否为0如果三数之和0则右指针需要往左移动如果三数之和0则左指针需要往右移动。这两种情况下不判断重复也没问题因为即使重复了和也不会是0不会被计入重复结果如果三数之和为0此时可以把三数存为三元组并存入结果数组中此后双指针都需要移动即左指针右移右指针左移并且移动的同时必须使用while语句判断重复情况切记while中需要附带lr移动至不出现重复即可。42.接雨水思路错误思路先减后增模块能接水的地方必定先减后增找到左右边界lr后雨水量min(height[l],height[r])*r-l-1-中间的柱子高度之和问题在于计算每个先减后增模块未必是对的例如[5, 1, 3, 2, 4]按照错误思路就是找到两个独立的先减后增模块后计算两部分雨水量之和但实际上这个的整体边界是54正确思路本题可采用双指针/单调栈/储存左右边界1双指针思路左右双指针向中间最高点逼近。每次比较双指针大小小指针向中间移动例如左指针更小则左指针和右侧height比较进行迭代每个点的水量等于该点的max(left-height[l])或者max(right-height[r])2储存左右边界思路先从左往右和从右往左遍历生成两个数组left_max和right_max其中left_max[i]表示第i个数左边所有数包括第i个数中最大的right_max[i]表示第i个数右边所有数包括第i个数中最大的那么第i个点的水量就会等于min(left_max[i]right_max[i]) - height[i]基于上述思想遍历所有点即可三.滑动窗口左指针和右指针形成动态窗口移动指针调整窗口大小本质为特殊的双指针通用步骤1.初始化左右指针通常都位于初始位置2.右指针不断右移扩大窗口3.当窗口满足条件时记录或更新结果左指针左移缩小窗口4.重复步骤23直至右指针到达末尾3.无重复字符的最长子串思路滑动窗口左指针固定右指针右移每个字符检查是否已经在集合中出现未出现则存入集合出现了则右指针固定左指针右移直至与右指针相同不管相同与否都要删除左指针在集合中对应的字符步骤同思路即可唯一要点左指针右移直至与右指针相同需要通过while实现条件为leftright and s[left] ! s[right]这样如果left初始位置就和right重复了第一下就不会进入循环优化思路使用字典结构左指针无需遍历。如果右指针的字符x出现在字典中对应位置为value则左指针直接移动到x的下一位(value1)然后更新x的位置为右指针(从之前的value改为现在的右指针)438.找到字符串中所有字母异位词思路本质上可以通过长度为3的滑动窗口遍历s中所有字符串然后每个字符串与p进行比较个人觉得难点在于异位词比较。简单思路是对两个异位词先排序然后直接比较即传统的.join(sorted())方法除此之外要注意s中获取m长的字符串的方式不能使用因为这样不仅耗时长而且后续还要清空前面的的字符。可以采取obj list(s[left:right])的方式降低时间复杂度优化思路使用数组存储p和s_3中每种字符的数量创建p_count [0]*26注意python中没有int arr[26] {0};这种写法仅能通过p [1,2,3,4,5]或者[0]*5或者循环的方式创建特定数组则p_count[p[i]-a] 1这样p_count中[i]就存储了26个字母中第i个字母出现的次数然后对比p_count和s_count是否一样即可进一步优化思路不在使用两个数组p_count和s_count分别存储字母数量仅使用一个p_count然后在遍历s的时候如果出现相同字母则对应位置的数组值-1最后通过判断p_count是否为0来判断字符串是否匹配PS注意比较数组时仅需考虑左右两个数即可因为窗口滑动时只有两个数会发生变化注意在C中字符是整数可以直接p_count[p[i]-a]。但是在python中得用ord函数即count[ord(p[i]) - ord(a)] 1且ord(a) 97ord(z) 122ord(A) 65ord(Z) 90四.子串子串字符串中连续的一段字符序列必须连续可以通过切片获取。560.和为K的子数组简单思路暴力穷举双循环从左往右遍历求和然后判断和是否和等于k错误思路双指针滑动窗口小于k则右指针右移大于k则左指针右移等于k则左右指针均右移以上思路仅适用于数组中的数为正数的情况完全没有考虑0和负数的情况。优化思路前缀和字典想要求解一个数组中某一连续段a-b的和除了把a-b的所有数累加之外还可以通过0-b的和减去0-a的和来实现。设定一个字典sumskey为累加和value为该在累加过程中累加和出现的次数。遍历存值sums[i]的过程中判断sums[i]-k是否已经出现在sums中如果出现则计数器1否则把sums[i]存入字典中。几个值得注意的点1字典需要存储出现次数而非索引i否则当同一个前缀和多次出现时索引值会被覆盖2字典初始化时不能为空字典而应该初始化为前缀和为0时出现次数为1即sums {0: 1}3如果s-k出现了多次应该计数s-k对应的value步骤for循环遍历累加对于每个循环得到的和s先检查s-k是否存在于字典中如果出现过就让count加上s-k对应的value即s-k出现次数。之后将当前前缀和s加入字典中然后value更新1。 一定要先判断s-k然后再更新s因为如果k0的话更新的s在每次循环时都会叠加误差。一定要初始化字典为{0: 1}不然sk的情况下即使满足了条件也不会被计入239.滑动窗口最大值错误思路仍然是暴力穷举从左往右遍历每k个数都找一次最大值并存到输出数组中显然这种做法会超时。PS如果要找一个数组列的最大值可以不用双循环直接用max函数max(nums[i:ik])切片仍然是左闭右开区间正确思路单调队列维护一个单调递减的双端队列队首始终是当前窗口的最大值队尾是最小值队列存储数的索引而非值以便于判断数是否还在窗口内遍历每个数如果它比队首大就把队首踢飞也把队列中所有比它小的数也踢飞也就是说队列中只剩它一个数如果它比队首小就正常入队具体规则1如果队列不为空且队首元素已经不在窗口内就移除队首2如果队列不为空且队列尾部的元素小于新加入的元素移除尾部元素3当滑动窗口形成时将队列头部元素当前滑动窗口的最大值加入结果列表76.最小覆盖子串错误思路遍历s所有长度不小于n的子串比较子串和t看包含关系是否成立。比较方法使用26*[0]数组记录t中每个字母的出现次数正确简化思路滑动窗口思想先右移右端点遍历至子串包含t然后右端点固定左端点右移直至子串不包含t。这种滑动窗口遍历思想会比全遍历的复杂度要低。判断s的子串是否涵盖t用变量geCnt维护当前子串窗口中有 geCnt 种字母的出现次数大于等于 t 中相应字母的出现次数。设 t 有 kinds 个不同的字母那么「子串每种字母的出现次数都大于等于 t 中相应字母的出现次数」等价于 geCntkinds。为了方便实现把 cntS 和 cntT 合并成一个 diff定义 diff[x]cntS[x]−cntT[x]。如果 diff[x]0就意味着窗口内字母 x 的出现次数和 t 的一样多。如果字母 x 进入窗口后diff[x]0这意味着 x 在子串和 t 中的出现次数从 变成了 ≥那么把 geCnt 增加一。如果字母 x 离开窗口前diff[x]0这意味着 x 离开窗口后x 在子串和 t 中的出现次数从 ≥ 变成了 那么把 geCnt 减少一。PS不能在 diff[x]≥0 的时候就把 geCnt 增加一。这样写的话对于同一个字母 xdiff[x] 等于 0,1,2,… 的时候都会让 geCnt 增加一这就重复统计了。思路来源76. 最小覆盖子串 - 力扣LeetCode判断子串涵盖的更复杂的操作代码简化Counter()函数统计字符串中字符统计列表中元素统计单词出现次数例如此外Count类重载了比较运算符比较两个Count对象时会逐个比较二者的键值对cnt_s cnt_t表示对于cnt_t中的每一个键cnt_s中对应键的计数都大于等于cnt_t中的计数从而实现判断涵盖功能。五.普通数组53.最大子数组和错误思路1.遍历 2.变形为正/非正交替的数组然后判断相邻正/非正之和的和去判断是否继续加入最大和中但是本质上无法解决跨越负数和仍然更大的问题。正确思路1.前缀和最大子数组和翻译为对于数组中的每一个位置j作为终点我们要找一个在它之前的位置i作为起点使得prefix_sum[j] - prefix_sum[i]最大所以当prefix_sum[j]固定时我们只需要让prefix_sum[i]最小即可步骤遍历数组维护三个变量当前前缀和(curr_sum0-i的数之和)当前最大和max_ans max(max_ans, curr_sum - min_sum)更新历史最小前缀和min_sum min(min_sum, curr_sum)2.Kadane算法动态规划要么延续前面的子数组要么从当前元素重新开始步骤维护一个关键变量以当前元素结尾的最大子数组和pre遍历数组for x in nums:更新pre的值pre max(pre x, x)更新最大值max_ans max(max_ans, pre)PS以当前元素结尾这一点完美的实现了对整个数组的遍历对该值的更新要么把下一个数加上来要么替换成下一个数。PS动态规划要点定义状态找转移方程。56.合并区间显然如果区间是有序的排序将非常简单思路先基于各区间的start从小到大排序然后记录一个[start,end]其初始值为intervals[0]。从左往右遍历存在三种情况1intervals[i1][0]endintervals[i1][1]则更新end intervals[i][1]2endintervals[i1][0]则将[start,end]添加到result中并更新[start,end]为intervals[i1]3endintervals[i1][1]此时什么都不做即可PS:切记循环结束后一定要单独 result.append([start,end])不然会漏最后一组结果PS列表元素排序优化intervals.sort(keylambda x: x[0])或者new_intervals sorted(intervals, keylambda x: x[0]).sort是原列表处理sorted是生成新列表。lambda函数是接收一个元素x返回x[0]189.轮转数组不考虑空间复杂度的思路显然可以将原数组拆分成两部分,0-n-k和n-k - n轮转的本质就是让左半去右边让右半去左边创建一个新数组复制原数组mid nums[:]或者mid nums.copy()然后for循环将mid的n-k - n赋值给nums的0-k将mid的0-n-k赋值给mid的k-n即可。PS注意两段for循环是根据nums确定的所以是0-k和k-n注意要考虑kn的情况此时添加k k % n即可优化思路空间复杂度为O(1):1.数组翻转先将nums翻转然后将[0,k%n − 1]区间的数组翻转然后将 [k%n,n−1] 区间的数组翻转通过第一次整体翻转换位置通过第二次局部翻转调顺序最终等效于实现了局部数组左移和右移PS:python中直接nums.reverse()可以直接实现对nums数组的翻转2.环状替换从nums[0]开始不断让其移动到目标位置这样只需要一个中间变量存储目标位置值即可。例如nums [1, 2, 3, 4, 5, 6, 7], k 3, n 7让nums[0]移动到nums[3]中间变量存储nums[3]然后nums[3]移动到目标nums[6]以此类推。但要注意可能存在多个环即一轮移动可能回到原点此时从数学上推导环的数量为gcd(n, k)n 和 k 的最大公约数每个环的长度为n / gcd(n, k)外层循环记录不同的起点循环条件为gcd(n, k)每次循环1即为新的起点因为起点和余数有关所以必定1即可内层循环为沿着环不断移动循环条件为回到原点238.除了自身以外数组的乘积思路禁用除法。考虑前缀/后缀分区。从左往右遍历累乘数组存入输出数组result中但是第i位的值为前i-1位的乘积第n位的值为前n-1位的乘积。从右往左遍历数组result[j] result[j] * mid其中mid为中间变量存储了从右往左的累乘结果第j轮循环时midnums[n-1]*nums[n-2]*...*nums[j1]41.缺失的第一个正数如果从1开始遍历数组寻找不存在的最小正整数时间复杂度为O(N2)空间复杂度为O(1)如果将数组转化为一个新的哈希表然后在哈希表中遍历查找时间复杂度为O(N)每次查找复杂度为O(1)空间复杂度为O(N)创建了一个新的哈希表要想满足时间复杂度为O(N)空间复杂度为O(1)考虑将数组下标当作哈希表的键值因为对于长度为n的数组缺失的最小正整数的范围一定在[1,n1]最差情况为1-n此时最小正整数为n1则将数组中值为i的数置换到下标为i1处最终得到的数组中如果第i位的数的值不是i-1则该位缺失。步骤从左往右遍历nums判断nums[i]是否在1-n之间且nums[i]是否等于nums[nums[i]-1]如果条件都满足则进行置换。注意置换需要使用循环因为置换后nums[i]的值变为nums[nums[i]-1]需要进一步判断其能否进行置换直至nums[i]不在1-n之间或者形成置换闭环置换全部完成后从左往右遍历nums如果出现nums[i] ! i1的说明该位置对应数缺失直接返回i1如果1-n所有位置上都符合则返回n1六.矩阵73.矩阵置零题目没有限制时间复杂度一个很简单的思路是遍历矩阵所有元素找到值为0的元素记录其行列下标。然后基于行列下标遍历矩阵将对应行和对应列的元素全部置零。如果行列号记录使用二维数组则额外空间为O(mn)如果行列号分开用两个数组记录则额外空间为O(mn)优化思路额外空间复杂度为O(1)使用矩阵第0行和第0列来存储0元素的行列号先单独判断第0行和第0列中有没有0并记录因为后续会更改第0行/列的值所以要提前记录然后遍历矩阵[1,1]到[m,n]如果有零则其行列号在第0行/列中更改为0。基于第0行/列的值选择矩阵行列赋0基于开始记录的值决定是否更改第0行/列的值为054.螺旋矩阵