欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

从最大子串到窗口滑动算法,我终于明白了为什么大多数搞算法的人头发会少了!

程序员文章站 2022-07-13 21:53:31
...

头发总在那么不经意间流逝。

今天忘忧跟大家一起搞定leetcode第三题,无重复字符的最长子串。

题目描述

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

示例 1:

  • 输入: “abcabcbb”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例2:

  • 输入: “bbbbb”
  • 输出: 1
  • 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例3:

  • 输入: “pwwkew”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。

请注意,你的答案必须是子串的长度,"pwke"是一个子序列,不是子串。

思路一(暴力法)

暴力法:没有暴力**不了的算法,如果有,那说明你不够暴力。

对字符串的每一个字符进行遍历。

  1. 声明两个索引,其中一个索引 i 标示当前匹配的开始位置的索引,另一个索引 j 标示当前匹配的位置。
  2. 判断字符串第 j 个位置的字符是否被[i, j)区间的字符所包含。如果包含,记录下索引 i 和索引 j 的差值作为当前遍历到的无重复元素的子串的长度, 并使索引 i 右移,j = i + 1,重复步骤2如果不包含,使 j 右移一位,重复步骤2
  3. 从所有子串长度中选取最大值作为返回结果。

具体代码实现如下:

/**
 * 暴力解法,获取最长的无重复的子串的长度
 * @param s 输入的字符串
 * @return 最大子串长度
 * 公众号:算法之灵魂拷问
 */
public static int lengthOfLongestSubstring(String s) {
    int length = s.length();
    int maxSubStrLength = 0;
    //i标记起始位置
    for (int i = 0; i < length; i++) {
        //j标记当前判断的位置
        for (int j = i; j < length; j++) {
            boolean flog = false;
            //判断字符串的[i, j - 1]的区间内有无跟第i个字符相同的字符
            for (int k = i; k < j; k++) {
                if(s.charAt(k) == s.charAt(j)){
                    flog = true;
                    break;
                }
            }
            //如果字符串的[i, j - 1]的区间内有跟第i个字符相同的字符
            if(flog){
                //当前所遍历的最大长度为之前的最大长度或者(j - i)中的最大值
                maxSubStrLength = Math.max(maxSubStrLength, j - i);
                break;
            }else{
                //如果不存在,当前所遍历的最大长度为之前的最大长度或者(j - i + 1)中的最大值
                //其中,加的1即为第i个元素
                maxSubStrLength = Math.max(maxSubStrLength, j - i + 1);
            }
        }
    }
    return maxSubStrLength;
}

解析:

暴力解法固然可以得到最终的结果,但是暴力解法的时间复杂度为O(n ^ 3), 运行效率是相当低的,那么有没有更好的方式呢?

思路二(滑动窗口法)

话不多说,直接上图!

从最大子串到窗口滑动算法,我终于明白了为什么大多数搞算法的人头发会少了!

滑动窗口法代码实现:

/**
 * 滑动窗口法
 * @param s 输入的字符串
 * @return 字符串最长无重复字串的长度
 * 公众号:算法之灵魂拷问
 */
public static int lengthOfLongestSubstring1(String s) {
    int length = s.length();
    if(length <= 1){
        return length;
    }
    //滑动窗口的右侧位置
    int right = 0;
    //滑动窗口的左侧位置
    int left = 0;
    //当前匹配到的最大子串长度
    int maxSubStrLength = 0;
    //窗口
    Set<Character> set = new HashSet<>(length);
    //遍历
    while(right < length){
        //如果窗口中包含即将划入窗口的元素
        if(set.contains(s.charAt(right))){
            //将窗口最左侧的元素移除
            set.remove(s.charAt(left++));
        }else{
            //如果窗口中不包含即将划入窗口的元素,那么将元素划入窗口
            set.add(s.charAt(right));
            //更新最大字串长度
            maxSubStrLength = Math.max(maxSubStrLength, set.size());
            //窗口右侧标记加一
            right++;
        }
    }
    return maxSubStrLength;
}

滑动窗口算法简介

滑动窗口算法,常用于解决一些字符串的字串,连续n个数的最大和,最小和等问题。
通过两个坐标(一般往右滑动的都是左闭右开)的方式,虚拟出一个固定大小或者动态大小的窗口,有效的节省了循环的次数,将原本的多次循环,循环嵌套等暴力解法的时间复杂度降低到了O(n)的级别。

生硬的文字没啥感觉,如果觉得还没懂,多看几遍图解或者把疑惑评价或者私信给我,忘忧尝试着给大家解惑

结束语:准备种子,就收获果实;准备努力,就收获成功;准备今天,就收获明天。

相关标签: 算法