企业官网建设流程全解析

3. 无重复字符的最长子串

一、问题描述

给定一个字符串s，请你找出其中不含有重复字符的最长 子串的长度。

示例 1:

输入:s = "abcabcbb"输出:3解释:因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入:s = "bbbbb"输出:1解释:因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入:s = "pwwkew"输出:3解释:因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。

二、思路：

1.定义字典存储下标和值，定义左指针=0

2.判断是否存在重复项且左指针小于重复项下标

3.若存在，则左指针 = 重复项下标+1

6.把当前字符的位置数字，存到以这个字符为键的字典里：record['w'] = 1，其中1为下标

三、代码

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: record = {} left = 0 len = 0 for right,c in enumerate(s): # 字符出现过，且下标>=left，说明在当前窗口内重复 # record[c]：去字典里取出 这个字符上一次出现的下标 if c in record and record[c]>=left: left = record[c]+1 record[c] = right len = max(len,right-left+1) return len

438. 找到字符串中所有字母异位词

一、问题描述

二、代码

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: res = [] n = len(s) m = len(p) if m>n: return res count_p = [0]*26 count_win = [0]*26 # 统计p的字母数量 for ch in p: count_p[ord(ch)-ord('a')] +=1 # 初始化第一个窗口 for i in range(m): count_win[ord(s[i])-ord('a')] +=1 # 判断第一个窗口 if count_win == count_p: res.append(0) # 滑动窗口，依次右移 for i in range(m,n): # 移除窗口左边旧字符 s[i-m] left_ch = s[i-m] count_win[ord(left_ch)-ord('a')] -= 1 # 加入新字符 s[i] new_ch = s[i] count_win[ord(new_ch)-ord('a')] += 1 # 对比是否异位词 if count_win == count_p: res.append(i-m+1) return res