Java 实现：找出字符串中最长无重复字符子串的长度

本文将介绍如何使用滑动窗口算法在 Java 中实现找出字符串中最长无重复字符子串长度的解决方案。

思路

使用滑动窗口来解决这个问题。

定义一个 HashMap 来存储字符及其在字符串中的位置。
定义两个指针，left 和 right，分别表示滑动窗口的左边界和右边界。
遍历字符串 s，每次移动右指针，如果遇到重复字符，则更新左指针的位置。
每次移动右指针时，都计算当前滑动窗口的长度，并更新最大长度。
最后返回最大长度即为不含重复字符的最长子串的长度。

代码

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            
            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

时间复杂度

O(n)，其中 n 为字符串的长度。

空间复杂度

O(m)，其中 m 为字符集的大小。在最坏情况下，字符集的大小为所有字符都不重复的情况。