longest-substring-without-repeating-characters
题目描述
Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 **子串** 的长度，"pwke" 是一个子序列，不是子串。<!--more-->
我的垃圾思路
One
- 刚开始想耍一些"小聪明"，看有没有巧妙的方法解决，当时用了类似于Node的前后'指针'的方式发现有线用例是过不了的
- 后面用到了类似"滑窗"的方法，碰到重复字符则将滑窗宽度归零，且位置回到被重复字符的下一位置。
- 但会出现死循环，因为没把之前被重复的字符
remove掉 -- 后面发现只remove掉那个重复的字符的话，有些没有重复的字符在回退之后再次计算的时候，会发生混乱<font color=grey size=2>(回退后再次走到之前不重复的字符时候，因为hash表中已经在第一次put过了，所以这次一定会发生重复情况)</font> - 所以上面把滑窗归零的时候是真正的归零，包括存数据的hash表
上面方法应该是 $ O(n^2) $ ,因为会发生例如abcdea在最后a发生重复，就会完全回退到b位置---so low ；提交记录耗时大概80+ms
Two
- 第二个方法是也两个指针类似滑窗， k指针一直前进，发生重复时j指针移动到被重复字符的下一位置，但是只能往右移动，不能回退
- 将
map<Character,Integer>中存放的之前被重复字符的value(即字符所在的索引)换为当前发生重复的字符位置 -- 不是被重复字符 - 循环中一直保持
max最大 - 当有其中一个指针到达终点时，就可以退出了 ；由于
j,k代表的都是索引，所以最后结果 为max+1
Three
- 第二种方法发现 k一直在++，其实就相当于for循环的 i++，所以就换成for循环了 -- 复杂度应该是 $ O(n) $
Two和Three 提交的耗时6ms,占用内存35M--占用内存竟然超过了 100%的java用户ヽ(°◇° )ノ
我的垃圾代码
package com.dasnnj.practice.medium;import java.util.HashMap;import java.util.Map;/** * Description <p> TODO: * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 * <p> * 示例 1: * <p> * 输入: "abcabcbb" * 输出: 3 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 * 示例 2: * <p> * 输入: "bbbbb" * 输出: 1 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 * 示例 3: * <p> * 输入: "pwwkew" * 输出: 3 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。</p> * * @author DASNNJ <a href="mailto:dasnnj@outlook.com.com"> dasnnj@outlook.com </a> * @date 2019-05-08 13:17 */public class LongestSubstringWithoutRepeatingCharacters { public static void main(String[] args) { LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters(); System.out.println(l.lengthOfLongestSubstring("")); } public int lengthOfLongestSubstring(String s) { //One /*char[] chars = s.toCharArray(); Map<Character, Integer> map = new HashMap<>(8); //计算非重复字符的长度 Integer len = 0; int max = 0; //索引 Integer index; for (int i = 0; i < chars.length; i++) { //如果是正常进行 //如果重复 if ((index = map.get(chars[i])) != null) { //回退到重复的位置，从重复位置的下一位重新算，相当于舍弃两个重复字符中的第一个 i = index; //长度归零 len = 0; //将map清空，从重复位置的下一位置重新计算 -- 清空是因为第一个重复的在上面提到是相当于舍弃，不清空的话会影响下次循环的判断 map.clear(); } else { //没重复当然正常put 正常++ map.put(chars[i], i); len++; } //每次循环都保持max最大 if (len > max) { max = len; } } return max;*/ if ("".equals(s)) { return 0; } char[] chars = s.toCharArray(); //j k,用于Two方法的两个指针---后面发现直接用for循环即可 int j = 0, k = 0, max = 0; Integer ele; Map<Character, Integer> sets = new HashMap<>(16); //Three for (int m = 0; m < chars.length; m++) { //如果发生重复 if ((ele = sets.get(chars[m])) != null) { // j指针指向两个重复字符中的第一个的下一位置，j指针不能后退，只能前进，所以下面有个判断 if (j < ele + 1) { j = ele + 1; } } //不重复则是正常put，重复情况1.将j指针指向原字符的下一位2.用新字符替换掉map中原字符（主要是为了替换map中key为此字符 的value值也就是索引） sets.put(chars[m], m); //每次循环保持max最大 if (max < m - j) { max = m - j; } } //Two 原理同Three /*while (j < chars.length && k < chars.length) { if ((ele = sets.get(chars[k])) != null) { if (j < ele + 1) { j = ele + 1; } } sets.put(chars[k], k); k++; if (max < k - j) { max = k - j; } }*/ return max + 1; }}