域网站名分类,全球虚拟主机论坛,深圳品牌策划vi设计,商城网站建设fwshop文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 窗口滑动2.2 基于哈希表的窗口滑动 1. 题目
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最… 文章目录 1. 题目2. 思路及代码实现Python2.1 窗口滑动2.2 基于哈希表的窗口滑动 1. 题目
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。
示例 2:
输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。
示例 3:
输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 字符串中任意个连续的字符组成的子序列称为该串的子串。 提示 0 s . l e n g t h 5 ∗ 1 0 4 0 s.length 5 * 10^4 0s.length5∗104s 由英文字母、数字、符号和空格组成
2. 思路及代码实现Python
题解来源力扣官方题解
2.1 窗口滑动
寻找字符串中不含重复字符的最长字串一个很直观的方法是找到无重复字符的所有子串其中最长的子串即为所求。
这里官方题解中用了一个双指针的方法左指针表示字串的起始位置 k k k右指针表示从当前左指针开始得到的最长无重复字符的子串的结束位置 r k r_k rk。这里值得注意的是当我们从 k k k 位置开始找到了一个无重复字符的最长子串其结束位置在 r k r_k rk则当我们滑动左指针到 k 1 k1 k1 时左指针到 r k r_k rk 之间仍然是无重复字符的子串。利用这个规律可以减少双指针窗口滑动过程的判断次数。
在Python当中判断是否包含重复值可以用列表list、集合set等存储无重复字符这里常用哈希集合set。在“窗口滑动”这个思路当中右指针是一直递增的而左指针也一直往右滑动两个指针都只滑动一遍整个字符串相当于每层循环乘以的系数之和为 n n n时间复杂度为 O ( n ) O(n) O(n)而空间复杂度为存储的无重复字符的子串在最差情况下存储了问题的字符集的全部元素。
class Solution:def lengthOfLongestSubstring(self, s: str) - int:# 哈希集合记录每个字符是否出现过occ set()n len(s)# 右指针初始值为 -1相当于我们在字符串的左边界的左侧还没有开始移动rk, ans -1, 0for i in range(n): # 左指针if i ! 0:# 左指针向右移动一格移除一个字符occ.remove(s[i - 1])while rk 1 n and s[rk 1] not in occ:# 不断地移动右指针occ.add(s[rk 1])rk 1# 第 i 到 rk 个字符是一个极长的无重复字符子串ans max(ans, rk - i 1)return ans执行用时244 ms 消耗内存17.02 MB
2.2 基于哈希表的窗口滑动
上面的双指针的操作很直观也很简单实现但是大家有没有发现当双指针窗口滑动的时候碰到一个新的重复字符时并不知道新的重复字符在原来子串当中的位置所以只能将左指针一格格地往右移动。
例如字符串“abcdc”当取到 “abcd” 子串时右指针滑动到最后一位 “c” 时判断得到该字符在已有子串中但是不知道具体位置所以左指针需要从“a” 移动到 “b” 再到 “c”而如果能直接存储每个字符的上一次出现的位置则在新增重复字符时直接将左指针移动到上一次出现的位置减少了左指针的遍历次数。
class Solution:def lengthOfLongestSubstring(self, s: str) - int:max_len, hashmap 0, {}# 定义窗口的首尾端 (start, end) 然后滑动窗口start 0for end in range(len(s)):# 存储字符的出现频率并更新子串最大长度hashmap[s[end]] hashmap.get(s[end], 0) 1if len(hashmap) end - start 1:max_len max(max_len, end - start 1)# 当满足下面条件时说明新增字符已经在哈希表当中此时更新 startwhile end - start 1 len(hashmap):head s[start]hashmap[head] - 1if hashmap[head] 0:del hashmap[head]start 1# 返回答案 (最大长度)return max_len执行用时68 ms 消耗内存17.02 MB
参考来源Eason
