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

dasnnj发布

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" 是一个子序列,不是子串。

我的垃圾思路

One

  1. 刚开始想耍一些"小聪明",看有没有巧妙的方法解决,当时用了类似于Node的前后’指针’的方式发现有些用例是过不了的
  2. 后面用到了类似"滑窗"的方法,碰到重复字符则将滑窗宽度归零,且位置回到被重复字符的下一位置。
  3. 但会出现死循环,因为没把之前被重复的字符remove掉 — 后面发现只remove掉那个重复的字符的话,有些没有重复的字符在回退之后再次计算的时候,会发生混乱(回退后再次走到之前不重复的字符时候,因为hash表中已经在第一次put过了,所以这次一定会发生重复情况)
  4. 所以上面把滑窗归零的时候是真正的归零,包括存数据的hash表

上面方法应该是 O(n^2) ,因为会发生例如abcdea在最后a发生重复,就会完全回退到b位置—so low ;提交记录耗时大概80+ms

Two

  1. 第二个方法是也两个指针类似滑窗, k指针一直前进,发生重复时j指针移动到被重复字符的下一位置,但是只能往右移动,不能回退
  2. map<Character,Integer>中存放的之前被重复字符的value(即字符所在的索引)换为当前发生重复的字符位置 — 不是被重复字符
  3. 循环中一直保持max最大
  4. 当有其中一个指针到达终点时,就可以退出了 ;由于j,k代表的都是索引,所以最后结果 为max+1

Three

  1. 第二种方法发现 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;
    }
}

0 条评论

发表评论

电子邮件地址不会被公开。