赞
踩
逻辑:
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成什么是滑动窗口?其实就是一个队列
,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列
!如何移动?我们只要把队列的左边的元素移出就行
了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!
参考视频:
一道算法题理解滑动窗思想!【趣刷Leetcode】 No.3 无重复字符的最长子串_哔哩哔哩_bilibili
class Solution { public int lengthOfLongestSubstring(String s) { // 哈希集合,记录每个字符是否出现过 Set<Character> set = new HashSet<Character>(); int left = 0, right = 0, length = 0, maxLength = 0; while (right < s.length()) { //如果当前字符不在set中 if (!set.contains(s.charAt(right))) { set.add(s.charAt(right)); length++;//当前set中的元素个数+1 maxLength = Math.max(length, maxLength);//更新最大长度 right++;//右指针移动 } else {//如果当前字符在set中,说明此时当前s[right]还无法添加进set //需要将和当前s[right](比如是'b')等值的上一个元素('b')及其之前的元素全部移出set //比如现在set中是(a,b,c),当前要进来的元素是b while (set.contains(s.charAt(right))) { //将和当前s[right]等值的上一个元素及其之前的元素全部移出set set.remove(s.charAt(left)); left++;//左指针向右移动 length--;//同时长度-- } set.add(s.charAt(right));//当前s[right]可以添加进set了 length++;//当前set中的元素个数+1 right++;//右指针移动 } } return maxLength; } }
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s
和 p
仅包含小写字母我们可以先创建一个大小为 26 的数组 c2来统计字符串 p 的词频,另外一个同等大小的数组 c1用来统计「滑动窗口」内的 s 的子串词频。当两个数组所统计词频相等,说明找到了一个异位组,将窗口的左端点加入答案。
public List<Integer> findAnagrams(String s, String p) { // 创建一个 ArrayList 用于存储结果,即字符串 s 中与字符串 p 构成异位词的子串的起始索引 List<Integer> ans = new ArrayList<>(); //获取输入字符串 s 和 p 的长度 int s_length = s.length(), p_length = p.length(); // 初始化两个大小为 26 的整型数组,用于统计字符出现的频率(因为是小写字母,所以范围是 a-z,共 26 个) int[] s_arr = new int[26], p_arr = new int[26]; // 遍历字符串 p,统计每个字符在 p 中的出现次数,并存入 p_arr 数组 for (int i = 0; i < p_length; i++) { p_arr[p.charAt(i) - 'a']++;//统计字符串 p 的词频 } // 双指针法,left 指向子串的起始位置,right 指向当前遍历到的字符位置 for (int left = 0, right = 0; right < s_length; right++) { s_arr[s.charAt(right) - 'a']++;// 统计「滑动窗口」内 s 的子串中当前字符的频率,并将其存入 s_arr 数组 //如果右边界-right已经超过了 p 的长度,则说明需要收缩左边界(即移除最左侧的字符) if (right - left + 1 > p_length) { s_arr[s.charAt(left++) - 'a']--; } // 检查 s 的子串(以 left 和 right 为边界的滑动窗口)的字符频率是否与 p 相同 if (check(s_arr, p_arr)) { ans.add(left);// 若相等,说明找到了一个异位词子串,将左边界 left 添加到结果列表 ans 中 } } // 返回包含所有异位词子串起始索引的结果列表 return ans; } //定义辅助方法 check(),比较两个字符频率数组 c1 和 c2 是否完全相等 boolean check(int[] c1, int[] c2) { for (int i = 0; i < 26; i++) { if (c1[i] != c2[i]){ // 遍历两个数组,只要有一个元素不相等就返回 false return false; } } // 所有元素都相等时返回 true return true; }
起始处理 p
串时,只对 cnt进行词频字符自增操作。当处理 s
的滑动窗口子串时,尝试对 cnt中的词频进行「抵消/恢复」操作。
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>();// 初始化结果列表,用于存储找到的异位词子串的起始索引 int s_length = s.length(), p_length = p.length();// 获取输入字符串 s 和 p 的长度 int[] cnt = new int[26];// 创建一个大小为 26 的整型数组 cnt,用于统计字符出现次数 for (int i = 0; i < p_length; i++) { cnt[p.charAt(i) - 'a']++;// 遍历字符串 p,对每个字符在 cnt 数组中进行计数 } int a = 0; for (int i = 0; i < 26; i++) if (cnt[i] != 0) a++;// 计算字符串 p 中不同字符的数量(即 cnt 中非零元素个数),并将其赋值给变量 a // 双指针法,left 指向子串起始位置,right 指向当前遍历到的字符位置 for (int left = 0, right = 0, b = 0; right < s_length; right++) { // 当滑动窗口右边界 right 向右移动时,将该位置字符在 cnt 中的计数减一,相当于抵消操作 if (--cnt[s.charAt(right) - 'a'] == 0) {//先对cnt[s.charAt(right) - 'a']进行减1,再判断是否=0 b++;// 如果抵消后计数变为 0,说明找到了一个新的与 p 字符频次相同的字符,b 自增 } // 当滑动窗口长度超过 p 的长度时,需要收缩左边界(移动 l) if (right - left + 1 > p_length) { // 对左边界字符在 cnt 中的计数加一,相当于恢复操作 if (++cnt[s.charAt(left++) - 'a'] == 1) { // 如果恢复后计数变为 1(之前为 0),说明移除了一个与 p 字符频次相同的字符,b 自减 b--; } } // 当 b 等于 a 时,表示当前子串的字符频次与 p 完全相同,是一个异位词,将子串起始索引添加进结果列表 if (b == a) { ans.add(left); } } // 返回包含所有异位词子串起始索引的结果列表 return ans; } }
public class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>();// 初始化结果列表,用于存储找到的异位词子串的起始索引 int s_length = s.length(), p_length = p.length();// 获取输入字符串 s 和 p 的长度 int[] cnt = new int[26];// 创建一个大小为 26 的整型数组 cnt,用于统计字符出现次数 for (int i = 0; i < p_length; i++) { cnt[p.charAt(i) - 'a']++;// 遍历字符串 p,对每个字符在 cnt 数组中进行计数 } // 双指针法,left 指向子串起始位置,right 指向当前遍历到的字符位置 for (int left = 0, right = 0, b = 0; right < s_length; right++) { cnt[s.charAt(right) - 'a']--; while (cnt[s.charAt(right) - 'a'] < 0) { cnt[s.charAt(left) - 'a']++; left++; } // 当 b 等于 a 时,表示当前子串的字符频次与 p 完全相同,是一个异位词,将子串起始索引添加进结果列表 if (right - left + 1 == p_length) { ans.add(left); } } // 返回包含所有异位词子串起始索引的结果列表 return ans; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。