Leetcode3--->无重复字符的最长子串长度

题目：给定一个字符串string，找出string中无重复字符的最长子串。

举例：

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be asubstring, "pwke" is a subsequence and not a substring.

思路：

首先，因为找的是无重复的子串，因此我们使用Hashset结构来存放已经找到的字符，HashSet中保存的是从某个位置pre到另一个位置i中间的所有字符。

从头开始遍历给定的字符串s, 每遍历一个，判断HashSet中是否有该字符，假设此时遍历到i位置：

1：如果没有，就将字符加入HashSet, 表明子串的长度又增大了一个，即prev~i位置的字符串是无重复字符的，更新最长字串的长度max_str;

2：如果有，就从prev位置开始循环遍历，直到找到与i位置字符相等的那个字符，然后prev指向那个字符位置+1的位置，i继续遍历。

直到i==len结束遍历。但此时还应该计算一次Max(i-prev, max_str)的大小，最后一次更新max_str的大小，返回最终的max_str;

扩展：

假设本题要求找出无重复的最长子串，则需要用两个变量保存窗口的左右位置，每当max_str更新的时候，就需要更新此时的窗口左右位置。最终使用s.substring(left, right)获取最长子串。

本题代码：

 public class Solution {

     public int lengthOfLongestSubstring(String s) {

         if(s == null || s.length() < 1)

             return 0;

         HashSet<Character> set = new HashSet<Character>();

         int pre = 0; // 窗口的左边界

         int max_str = Integer.MIN_VALUE; // 最长字串长度

         int i = 0; // 窗口的右边界

         int len = s.length();

         while(i < len)

         {

             if(set.contains(s.charAt(i))) // 找到与i位置相等的那个字符，pre指向该字符的下一个位置，重新开始窗口

             {

                 if(i - pre > max_str)

                     max_str = i - pre;

                 while(s.charAt(pre) != s.charAt(i))  //直到找到与当前字符相等的那个字符，然后才可以重新开始新一轮的窗口计数

                 {

                     set.remove(s.charAt(pre));

                     pre ++;

                 }

                 pre ++;

             }

             else

             {

                 set.add(s.charAt(i));

             }

             i++;

         }

         max_str = Math.max(max_str, i - pre); // i一直向后，直到超出s的长度，此时也要计算窗口的大小

         return max_str;

     }

 }

巴特西

Leetcode3--->无重复字符的最长子串长度

最新文章

热门文章