leetcode hot100【LeetCode 3. 无重复字符的最长子串】java实现

LeetCode 3. 无重复字符的最长子串

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释:最长的无重复字符的子串是 "wke",其长度为 3。

提示:

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母组成

Java 实现代码

import java.util.HashMap;

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

解题思路

  1. 滑动窗口:使用两个指针 leftright 表示当前子串的边界。
  2. 哈希表:用一个哈希表存储字符及其最新出现的位置。
  3. 遍历字符串
    • 当遇到重复字符时,更新 left 指针,以确保子串中没有重复字符。
    • 更新哈希表中的字符位置,并计算当前子串的长度,更新最大长度。

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串的长度,滑动窗口遍历了字符串一次。
  • 空间复杂度:O(min(n, m)),其中 n 是字符串的长度,m 是字符集的大小。哈希表的空间复杂度与字符集大小有关。
上一篇:Linux第一个小程序-进度条


下一篇:【开源免费】基于SpringBoot+Vue.JS新闻推荐系统(JAVA毕业设计)