leetcode:无重复字符的最长字串(详解)-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode:无重复字符的最长字串(详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目描述？

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

leetcode:无重复字符的最长字串(详解),leetcode,算法,java

二、题解

方案一：容易理解（时间复杂度O(n)）

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

HashMap<Character, Integer> map = new HashMap<>();创建一个HashMap，用于存储字符及其最后一次出现的位置。
int max = 0;: 用于记录最长子串的长度。
int start = 0;: 用于记录当前子串的起始位置。
for (int i = 0; i < s.length(); i++) {: 遍历输入字符串。
char ch = s.charAt(i);: 获取当前遍历到的字符。
if (map.containsKey(ch)) { … }: 如果当前字符已经在子串中出现过。
start = Math.max(map.get(ch) + 1, start);: 更新子串的起始位置，确保不包含重复字符。
max = Math.max(max, i - start + 1);: 计算当前子串的长度并更新最大长度。
map.put(ch, i);: 将字符及其位置放入HashMap。
最后返回最长子串的长度 max。

方案二：滑动窗口（时间复杂度O(n)）

  public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }