中山外包网站设计地推拉新接单网

算法系列之滑动窗口

题目

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

示例 1:输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

解题思路

使用滑动窗口算法
滑动窗口算法的核心思想是在一个给定的序列（如数组或字符串）上定义一个窗口，该窗口可以根据特定的条件进行动态调整。窗口的大小可以固定，也可以根据问题的需求动态变化。在滑动过程中，通过不断更新窗口的边界和内部元素的状态，我们能够高效地获取所需的信息，如最大、最小子序列和，满足特定条件的子序列等。​

想象一个在序列上滑动的窗口，就像一个移动的框，它可以从序列的起始位置开始，每次移动一个单位（或根据具体情况移动多个单位）。在每一步移动中，窗口会 “吸入” 新的元素，同时 “吐出” 离开窗口范围的元素。通过对窗口内元素的实时计算和记录，我们可以在不遍历整个序列的情况下，快速找到满足特定条件的子序列。

• 算法原理
  • 初始化：设置左右指针left和right，通常都指向数据结构的起始位置。
  • 窗口滑动：
    • 扩展右边界：通常先移动right指针来扩展窗口的右边界，直到窗口内的元素不再满足特定条件或right指针到达数据结构的末尾。
    • 收缩左边界：在窗口不满足条件时，移动left指针来收缩窗口的左边界，直到窗口内的元素重新满足条件。
  • 记录结果：在窗口滑动的过程中，记录下满足条件的中间结果（如最大值、最小值、子串长度等）。
  • 重复步骤：重复步骤2和3，直到right指针遍历完整个数据结构。

获取某个字符串中不重复的字符长度，如abfhdasdrbch
//abfhdasdrbch//思路// 索引-字符-不重复字符串-重新开始//0-a-a  (开始位index=0即a)//1-b-ab//2-f-abf//3-h-abfh//4-d-abfhd//5-a-bfhda（a重复了，所以需要重新开始，新的开始位，index=1即b）//6-s-bfhdas//7-d-asd (又重复了，新的开始位，index=5即a)//8-r-asdr//9-b-asdrb

public static  int getBig(String s){//最大长度int max=0;//下一段不重复开始发起始索引号int startIndex=0;//字符对应最新的索引号HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();int length = s.length();for (int i = 0; i < length; i++) {Integer charIndex = characterHashMap.get(s.charAt(i));if (charIndex!=null){// 如果字符已经存在于哈希表中，并且其位置在窗口内，则移动左边界startIndex=Math.max(charIndex+1,startIndex);}characterHashMap.put(s.charAt(i),i);max=Math.max(max,i-startIndex+1);}return max;
}