/**
 * 无重复最长子串
 * 思路1：暴力拆解法
 */
public class Solution1 {

    /**
     * 暴力思路：相当于遍历每个子串，校验子串是否重复
     * 遍历每个元素i，判断以当前元素为起点的子串（i,j）是否包括重复元素。如果包括重复元素则更新max
     */
    public int lengthOfLongestSubstring(String s) {
        // 定义最大子串的长度
        int max = 0;

        // 校验以每个元素为起点的子串(此处子串是以i为起点，j为终点)
        for(int i = 0; i < s.length(); i++) { // i 为 当前元素（表示子串的起点）
            for(int j = i + 1; j < s.length(); j++) { // j 为子串的终点
                // 判断子串(i,j)是否包括重复元素，如果不包括则更新max
                if(!validSubStrRepeat(s.substring(i,j))){
                    // 如果子串不包括重复元素，则更新max
                    max = Math.max(max, j - i) ;
                }
            }
        }
        // 返回结果
        return max;
    }

    // 校验子串中是否包含重复元素（可以通过哈希表来校验）
    public boolean validSubStrRepeat(String subStr) {
        // 方式1：HashSet存储的是非重复元素，此处可以依次入集合然后判断size大小是否一致

        // 方式2：集合迭代，判断元素是否已存在，如果存在则说明重复
        List<Character> list= new ArrayList<>();
        for(int i = 0; i < subStr.length(); i++) {
            // 如果出现重复元素，直接返回true
            if(list.contains(subStr.charAt(i))) {
                return true;
            }
            list.add(subStr.charAt(i));
        }
        return false;
    }
}

这种实现思路的算法时间复杂度为O(n³)，当输入的数组规模变大的时候其效率非常低下

👻方法2：滑动窗口

首先理解滑动窗口的含义，滑动窗口实际是一个队列。例如abcabcbb，基于此来分析一下这个滑动窗口的演变：

一开始进入这个队列（窗口）为a（此处分为p、q左右指针），此时队列依然满足要求，因此队列的q指针继续向右移动变为ab，每次移动都会记录当前窗口的大小（队列长度）
类似的，ab窗口满足题目要求，q 指针向右移动变为abc，依次类推
当abc窗口满足要求，q指针向右移动，此时进入a时，当前窗口变为abca存在重复字符，因此需要移动 p 指针将左边的元素逐步移出，直到满足要求
基于此，一直维持这样的队列，找出队列最长解

核心实现思路：使用一个HashSet来实现滑动窗口，用来检查重复字符。维护开始和结束两个索引，默认都是从0开始，然后随着循环【向右移动结束索引】，遇到不是重复字符则放入窗里，遇到重复字符则【向右侧移动开始索引】，直到左右指针都遍历到数组尾部，最终得到结果

定义左右指针（初始化从0开始），定义Set集合作为滑动窗口（因为只需要得到满足条件的子串长度，因此只需要考虑不重复的问题，而不需关注元素存储的有序性）
定义循环的临界条件（左右指针都遍历到数组尾部），在这个条件内依次校验响应的规则
- 如果set中不包含右指针指向的字符，则更新窗口、右指针右移
- 如果set中包含右指针指向的字符，则逐步收缩，将左指针右移（此处并不是直接就能够移出重复元素，而是逐步将left边界右移，直到将重复元素移出，在下一次遍历时，因为这个重复元素在前面的遍历过程中从窗口移出了，则其会通过当前的right指针指向重新加入窗口
- 每次循环结束都更新下窗口的最大值

/**
 * 3.无重复字符的最大子串
 * 思路：滑动窗口
 * 使用一个HashSet来实现滑动窗口，用来检查重复字符。 维护开始和结束两个索引，默认都是从0开始，然后随着循环【向右移动结束索引】，遇到不是重复字符则放入窗里，遇到重复字符则【向右侧移动开始索引】，最终得到结果
 */
public class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        // 定义结果
        int res = 0;

        // 定义左右指针，初始化从0开始
        int left = 0,right = 0;

        // 定义用于判断重复的Set集合（窗口）（因为要获取的是长度，所以不用考虑集合元素的有序性）
        HashSet<Character> set = new HashSet<Character>();

        int n = s.length();
        while (left < n && right < n) {
            // 判断当前窗口是否满足要求，进而决定指针移动位置
            if(!set.contains(s.charAt(right))) {
                // 更新窗口，将right指针右移
                set.add(s.charAt(right++));
            }else{
                // 存在重复元素，直接移除（此处只考虑窗口元素个数/内容，不考虑有序性），并将left指针右移
                set.remove(s.charAt(left++)); 
            }
            // 更新当前窗口的最大值
            res = Math.max(res, set.size());
        }
        return res;
    }
}

3.复盘

🟡02-找到字符串中所有字母异位词（438）

1.题目内容

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序

s = "cbaebabacd", p = "abc"：
- 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词
- 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词

2.题解思路

👻方法1：暴力解析

类似暴力解析的概念，只不过此处要找的子串长度是固定的，所以复杂度也相对较低（思路是找字符串的所有子串，然后判断子串是否为target的字母异位词即可），所谓字母异位词就是满足排序后字符序列相同，因此可以先将target进行排序，然后再对比每个符合的子串

核心思路
- 循环遍历字符串的每个元素
  - 以每个元素为起点，检索对应固定长度（target）的子串，将这个子串排序后与target进行比较，满足条件则将当前索引加入结果集

public class Solution1 {

    /**
     * 字母异位词：排序后的序列相同
     * 暴力法：
     */
    public List<Integer> findAnagrams(String s, String p) {

        // 定义返回结果
        List<Integer> res = new ArrayList<Integer>();

        int sLen = s.length();
        int pLen = p.length();

        // 对目标字符串进行排序
        char[] pArr = p.toCharArray();
        Arrays.sort(pArr);
        String sortedP = String.valueOf(pArr);

        // 遍历判断以每个元素为起点，其对应子串是否满足字母异位词要求
        for (int i = 0; i < sLen - pLen + 1; i++) {
            // 排序后的序列相同
            String subStr = s.substring(i, i + pLen);
            char[] subArr = subStr.toCharArray();
            Arrays.sort(subArr);
            String sortedSub = String.valueOf(subArr);
            if (sortedP.equals(sortedSub)) {
                // 满足字母异位词要求，将索引加入结果集
                res.add(i);
            }
        }

        // 返回结果集
        return res;
    }
}

👻方法2：滑动窗口

s 源字符串、p目标字符串，对于字母异位词的切入可以有两点：排序后的字符序列是一致的 或者字符串中的对应字符个数一致。此处采取的思路是用于判断排序后的字符序列是否一致

先将p目标字符串进行排序（目的是将其与窗口进行对比）
定义一个滑动窗口（左右指针left，right），left起始值为0、right起始值为p的大小（目的是为了设置一个和p字符串相同size的窗口）
滑动窗口进行遍历：当窗口right指针到达s尾部则遍历结束
- 滑动过程中需要判断当前窗口排序后的序列和目标序列是否一致，一致则将索引记录到结果集，并继续滑动（左右指针都向右移动）

/**
 * 438.找到字符串中所有字母异位词
 * 字母异位词：可以从两个点切入，排序后的字母序列是一致的 或者 字符串中每个字符出现的个数是一样的
 */
public class Solution {

    /**
     * @param s 原字符串
     * @param p 目标字符串
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        // 定义结果
        List<Integer> res = new ArrayList<Integer>();

        // 对目标字符串进行排序
        char[] pArr =  p.toCharArray();
        Arrays.sort(pArr);
        p = new String(pArr);

        // 定义滑动窗口的左右指针
        int left = 0,right = pArr.length;

        // 当窗口移动到数组尾部则结束
        while(right<=s.length()){
            // 判断窗口队列排序后的序列是否和排序后的p一致
            char[] subArr = s.substring(left,right).toCharArray();
            Arrays.sort(subArr);
            if(p.equals(String.valueOf(subArr))){
                res.add(left);
            }
            // 窗口右移（左右指针右移）
            left ++;
            right ++;
        }

        // 返回结果
        return res;
    }
}

复杂度分析

时间复杂度：
空间复杂度：

3.复盘

昵称

邮箱

网址

按正序
按倒序
按热度

hot100-03-滑动窗口

预览: