LeetCode - 3

题目描述

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

示例 1:

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

示例 2:

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

解题思路

双指针

使用快慢指针i、j 来指向子串的头和尾，用k指针在i、j之间遍历寻找是否有重复的字母出现，有重复则更新i，即子串的起始位置。

int i = 0, max = 0;
char[] chars = s.toCharArray();

for (int j = 0; j < s.length(); j++) {
    for (int k = i; k < j; k++)
        if (chars[k] == chars[j]) {
            i = k + 1;
            break;
        }
    max = Math.max(j - i + 1, max);
}
return max;

滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。

窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 $$[i, j)$$（左闭右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

例如，我们将 $$[i, j)$$ 向右滑动 1个元素，则它将变为 $$[i+1,j+1)$$（左闭右开）。

public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                  j++;
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i));
                  i++;
            }
        }
        return ans;
    }

改进的滑动算法

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }

使用数组来代替Map

当字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

• int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’ ，如果建一个26位的数组，需要将 char-65 或 char-97来保证 A、a 从index = 0 开始
• int [128] 用于ASCII码，一般用这个就够了
• int [256] 用于扩展ASCII码

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // 当前字母char的下标，如果是a-z的话直接从97开始
        
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);  //不用强转成int，能自动识别
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }

感谢：LeetCode
部分参考自：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/

本文链接：