Leetcode03 用滑动窗口思想来解决字符串问题

什么是滑动窗口思想：

滑动窗口是一种算法技巧，用于解决一类涉及子串/子数组的问题。滑动窗口可以通过定义两个指针（通常是左右指针或起始和结束指针），来构建一个可变大小的窗口，从而在给定的数据结构（如字符串或数组）上移动窗口，并实时更新窗口内的状态。滑动窗口算法的基本思想是：

初始化窗口的左右边界，使窗口包含初始的元素或子串。
不断移动右边界，扩大窗口，同时根据问题要求进行相应的操作（如计算最小值、最大值、求和等）。
如果窗口内的状态满足某个条件，尝试缩小窗口，即移动左边界，继续进行步骤2。
重复步骤2和3，直到右边界到达数据结构的末尾。

滑动窗口主要分为两大类，一种是长度固定的滑动窗口，一种是长度动态变化的滑动窗口。滑动窗口的难点在于如何向窗口中添加元素、如何缩小窗口、何时更新结果。

例题：

题目：

给定一个字符串 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 由英文字母、数字、符号和空格组成

哈希表理解：

Leetcode03 用滑动窗口思想来解决字符串问题

2.有一个更清晰简介的理解思路：

Leetcode03 用滑动窗口思想来解决字符串问题

我的代码（未完善）：

//滑动窗口思想
    public static void main(String[] args) {
        System.out.println("请输入字符串");
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char [] arr = s.toCharArray();
        System.out.println("你输入的字符数组arr[]：");
        for (int i = 0; i  
次还需要后续补充（哈哈，别忘了）
网上比较简洁快速的代码：
不太理解这个代码含义（呜呜呜，哭死）：
class Solution {
    public int lengthOfLongestSubstring(String s) {
 int right=0,left=0,a,max=0;
    while(s.length()!=left){
    a = s.indexOf(s.charAt(left),right);
    if(a!=left){
        right=a+1;
    }
    max=Math.max(max,left-right+1);
    left++;
}
return max;
    }
}
                                                        本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/47a70c2a35.html

Leetcode03 用滑动窗口思想来解决字符串问题

相关推荐