「力扣」第 3 题:无重复字符的最长子串(滑动窗口典型问题)


「力扣」第 3 题:无重复字符的最长子串(滑动窗口典型问题)

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

方法一:暴力解法

  • 枚举这个字符串的所有子串;

  • 对于每一个子串都判断一下这个子串是否有重复字符;

  • 在从没有重复字符的所有子串中找出长度最长的那个,返回即可。

伪代码:

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();

        int maxLen = 1;
        for (int left = 0; left < len - 1; left++) {
            for (int right = 0; right < len; right++) {
                String subString = s.substring(left, right + 1);
                if (subString 不包含重复元素){
                    maxLen = Math.max(maxLen, subString.length());
                }
            }
        }
        return maxLen;
    }
}

方法二:滑动窗口

性质:如果在子区间 [left, right] 中有重复元素,[left, right + 1][left, right + 2] 一直到 ``[left, len - 1]一定包含重复元素。此时就得考虑移动left` 变量。

注意:

  • int[] hashMap = new int[128]; 为了防止空格的出现,所以设置得大一点;

  • 只要是右边界 right 在窗口里出现了 $2$ 次,就得不断将左边界从窗口里删除,所以使用 while

Java 代码:

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) {
            return len;
        }

        char[] charArray = s.toCharArray();

        int left = 0;
        int right = 0;

        // 描述 [left, right) 里是否有元素的变量
        int[] hashMap = new int[128];
        // [left, right) 无重复的元素
        int res = 1;
        while (right < len) {
            hashMap[charArray[right]]++;
            if (hashMap[charArray[right] ] == 2) {
                while (hashMap[charArray[right]] == 2) {
                    hashMap[charArray[left]]--;
                    left++;
                }
            }
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }
}

Java 代码:

for 循环的写法:

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) {
            return len;
        }

        char[] charArray = s.toCharArray();
        // 描述 [left, right) 里是否有元素的变量
        int[] hashMap = new int[128];
        // [left, right) 无重复的元素
        int res = 1;
        for (int left = 0, right = 0; right < len; right++) {
            hashMap[charArray[right]]++;
            if (hashMap[charArray[right]] == 2) {
                while (hashMap[charArray[right]] == 2) {
                    hashMap[charArray[left]]--;
                    left++;
                }
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

方法三:滑动窗口 + 哈希表优化

思路:记录下每个字符出现的最新的下标。

Java 代码:

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        // 特判
        if (len < 2) {
            return len;
        }

        int res = 1;
        // key:数值,value:最新的下标
        Map<Character, Integer> map = new HashMap<>(len);
        char[] charArray = s.toCharArray();

        int left = 0;
        int right = 0;
        // [left, right) 没有重复元素
        while (right < len) {
            Character c = charArray[right];
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            right++;

            res = Math.max(res, right - left);
        }
        return res;
    }
}
  • 使用数组代替哈希表

Java 代码:

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        // 重复元素上一次出现的位置很重要
        int len = s.length();
        if (len < 2) {
            return len;
        }

        int[] window = new int[128];
        for (int i = 0; i < 128; i++) {
            window[i] = -1;
        }

        char[] charArray = s.toCharArray();

        int res = 1;
        int left = 0;
        // [left, right) 没有重复元素
        for (int right = 0; right < len; right++) {
            if (window[charArray[right]] != -1) {
                left = Math.max(left, window[charArray[right]] + 1);
            }
            window[charArray[right]] = right;
            // 注意理解这里为什么是 + 1
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 26 题:删除排序数组中的重复项 「力扣」第 26 题:删除排序数组中的重复项
「力扣」第 26 题:删除排序数组中的重复项 中文网址:26. 删除排序数组中的重复项 ; 英文网址:26. Remove Duplicates from Sorted Array 。 给定一个排序数组,你需要在原地删除重复出现的元素,
下一篇 
「数组」专题 3:三路快排 partition 的应用 「数组」专题 3:三路快排 partition 的应用
「数组」专题 3:三路快排 partition 的应用
  目录