• 82305

    文章

  • 735

    评论

  • 18

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

【leetcode算法-无重复字符的最长子串】

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>

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

示例 1:

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


示例 2:

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

1、暴力破解

package leetcode;

import java.util.HashSet;

public class Demo2 {

	public static int LengthOfLongestSubstring(String str)
    {
        int resLength = 0;
        int strLength = str.length();
        HashSet<String> hashSet = new HashSet<String>();
        for (int i = 0; i < strLength; i++)
        {
            for (int j = i + 1; j < strLength; j++)
            {
                //这里能确定str的所有子串

            	String strChildren = str.substring(j, j+1);
                if (hashSet.contains(strChildren))
                {
                    break;
                }
                else
                {
                    hashSet.add(strChildren);
                }
               
            }
        }
        return resLength; 
    }
	public static void main(String[] args) {
		
		System.out.println(Demo2.LengthOfLongestSubstring("ababedf"));
	}

}

2、大佬解法

    滑动窗口,通过使用 HashSet 作为滑动窗口,我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。滑动窗口是数组/字符串问题中常用的 抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j)向右滑动 1 个元素,则它将变为 [i+1, j+1)(左闭,右开)。

     回到我们的问题,我们使用 HashSet 将字符存储在当前窗口 [i, j)(最初 j = i)中。 然后我们向右侧滑动索引 j,如果它不在 HashSet 中,我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时,我们找到的没有重复字符的最长子字符串将会以索引 i开头。如果我们对所有的 i 这样做,就可以得到答案。

     2.1、代码实现

public static int LengthOfLongestSubstring3(String str)
	 {
	     int resLength = 0;
	     int strLength = str.length();
	     int i = 0, j = 0;
	     HashSet<String> hashSet = new HashSet<String>();
	 
	     while (i < strLength && j < strLength)
	     {
	    	 String oneStrJ = str.substring(j,j+1);
	         if (!hashSet.contains(oneStrJ))
	         {
	             hashSet.add(oneStrJ);
	             j++;
	             resLength = Math.max(resLength,j-i);
	         }
	         else
	         {
	        	 String oneStrI = str.substring(i, i+1);
	             hashSet.remove(oneStrI);
	             i++;
	         }
	     }
	     return resLength;
	 }

      2.2 代码实现:

     (1)快指针j所在元素不重复,更新max,将快指针j元素在hash表中的标记为出现,后移j ;
     (2)快指针j所在元素重复,慢指针后移,此时将慢指针i元素在hash表中的标记清除。此时并不关心是谁重复,重复元素前的元素都要清除掉。

	public static int lengthOfLongestSubstring(String s) {
        int []hash = new int [500];
        int max = 0;
        int i = 0, j = 0;

        while (i < s.length() && j <s.length() ) {
            if(hash[s.charAt(j)] == 0) {
                hash[s.charAt(j)] = 1;
                j++;
                max = (j - i) > max ? (j - i) : max;
            } else {
                hash[s.charAt(i)] = 0;
                i++;
            }  
        }
        return max; 
    }

 


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

欢迎来到梁钟霖个人博客网站。本个人博客网站提供最新的站长新闻,各种互联网资讯。 还提供个人博客模板,最新最全的java教程,java面试题。在此我将尽我最大所能将此个人博客网站做的最好! 谢谢大家,愿大家一起进步!

转载原创文章请注明出处,转载至: 梁钟霖个人博客www.liangzl.com

1条评论

Loading...
  • 901L

    第一个暴力方法行不通啊,如果输入“cdd”j=i+1了就直接把c略过了



发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤
注册梁钟霖个人博客