2026.7.1
📅 2026/7/2 13:27:51
👁️ 阅读次数
📝 编程学习
1.无重复字符的最长字串。
可以记住下面这段话:
滑动窗口的本质就是维护一个始终满足题目要求的连续区间。这道题中,窗口内始终不能有重复字符。右指针从第一个字符开始不断向右扩展窗口,尝试加入新的字符;如果加入后出现重复,就不断移动左指针缩小窗口,直到窗口重新合法。这样,对于每一个右指针位置,窗口都是以它为右边界的最长无重复连续子串,再不断更新窗口长度即可得到最终答案。整个过程中左右指针都只向右移动,因此时间复杂度为 O(n)。
2.字母异位词
首先判断
s的长度是否小于p,如果小于,说明s中不可能存在长度为len(p)的子串,因此直接返回空列表。然后使用两个长度为 26 的数组p_count和s_count分别统计p和s的第一个长度为len(p)的窗口中每个字母出现的次数。初始化完成后,如果两个数组相等,说明第一个窗口就是p的异位词,将下标0加入结果。接着开始滑动窗口,从下标len(p)开始遍历s。每次滑动时,将右边新进入窗口的字符对应的计数加一,再将左边离开窗口的字符对应的计数减一,这样窗口大小始终保持为len(p)。每完成一次更新s_count,就比较p_count和s_count是否完全相同,如果相同,说明当前窗口是p的一个异位词,将当前窗口的起始下标加入结果列表。最后返回结果列表。整个过程中窗口长度始终保持为len(p),因此时间复杂度为 O(n)。
编程学习
技术分享
实战经验