题目地址(3. 无重复字符的最长子串)

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目描述

  1. 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
  5. 示例 1:
  7. 输入: s = "abcabcbb"
  8. 输出: 3 
  9. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  12. 示例 2:
  14. 输入: s = "bbbbb"
  15. 输出: 1
  16. 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
  19. 示例 3:
  21. 输入: s = "pwwkew"
  22. 输出: 3
  23. 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  24.      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
  27. 示例 4:
  29. 输入: s = ""
  30. 输出: 0
  35. 提示：
  37. 0 <= s.length <= 5 * 104
  38. s 由英文字母、数字、符号和空格组成

前置知识


公司

  • 暂无

思路

image.png
滑动窗口 遇到相同的字符就把i从之前相同的的下一个开始

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int lengthOfLongestSubstring(String s) {
  4.         //128是因为一会要是用ASCII码 z是一百二十多
  5.         int[] ints = new int[128];
  6.         //返回值
  7.         int res = 0;
  8.         for (int left = 0, right = 0; right < s.length(); right++) {
  9.             //左指针为当前值 还是 在ints里s对应的字符位置的数字
  10.             //取决于数组这个位置是否有数字 也就是有没有重复的字符
  11.             //如果有重复的字符 因为记录的是下个字符的下标 就让left=之前重复的下一个字符
  12.             left = Math.max(ints[s.charAt(right)], left);
  13.             //记录最大的数组的长度 如果只有一个字符长度为1
  14.             res = Math.max(res, right - left + 1);
  15.             //记录当前字符的下一个字符的下标
  16.             ints[s.charAt(right)] = right+1;
  17.         }
  18.         return res;
  19.     }
  20. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：3. 无重复字符的最长子串 - 图2#card=math&code=O%28n%29&id=J3Q9x)
  • 空间复杂度：3. 无重复字符的最长子串 - 图3#card=math&code=O%28n%29&id=Zkhp6)