面试 – 第2页 – gitweixin

Java, 面试 12月 22,2024

大厂面试手撕面试题:一个字符串中最长的没有重复字符的子串（亲测可用的java实现)

要解决 “求解一个字符串中最长的没有重复字符的子串” 的问题，可以使用 滑动窗口（Sliding Window）算法。这个算法通过维护一个动态窗口来跟踪当前没有重复字符的子串，然后逐步扩展窗口来找到最长的子串。

思路：

使用两个指针，left 和 right，表示当前窗口的左右边界。
通过哈希集合（HashSet 或 HashMap）来存储窗口中的字符，确保每个字符在窗口内唯一。
从左到右遍历字符串，每次右指针right向右移动，检查字符是否已经在窗口中存在。如果存在，就将左指针left向右移动，直到窗口中没有重复字符。
更新最长子串的长度。

Java实现：

import java.util.HashSet;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        // 哈希集合用于存储窗口中的字符
        HashSet<Character> set = new HashSet<>();
        
        // 定义左右指针和最大长度
        int left = 0;
        int maxLength = 0;
        
        // 右指针向右移动，遍历字符串
        for (int right = 0; right < s.length(); right++) {
            // 如果右指针指向的字符在集合中，说明有重复字符
            // 移动左指针直到去除重复字符
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            
            // 将当前字符加入集合
            set.add(s.charAt(right));
            
            // 更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("The length of the longest substring without repeating characters is: " + lengthOfLongestSubstring(s));
    }
}

解释：

HashSet<Character> set = new HashSet<>();：
- 用于存储当前窗口内的字符，确保窗口内的字符唯一。
left 和 right 指针：
- right指针用来遍历字符串。
- left指针控制窗口的起始位置，确保窗口内没有重复字符。
滑动窗口的调整：
- 当遇到重复字符时，移动left指针，直到窗口内不再有重复字符。
- 每次移动时，都会更新maxLength，保持最大窗口的长度。
时间复杂度：
- 最坏情况下，left 和 right 每个指针最多各走一次字符串，因此时间复杂度是 O(n)，其中 n 是字符串的长度。

示例输出：

对于输入 "abcabcbb"，输出结果是：

The length of the longest substring without repeating characters is: 3

该子串是 "abc"，其长度为 3。

作者 east

分类归档面试