No.003：Longest Substring Without Repeating Characters

问题：

Given a string, find the length of the longest substring without repeating characters.
Example:
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 a substring, "pwke" is a subsequence and not a substring.

官方难度：

Medium

翻译：

给定一个字符串，找出最长子串的长度，且在子串中无重复字符。

例子：

字符串1：“abcabcbb”，长度为3。

字符串2：“bbbbb”，长度为1。

字符串3：“pwwkew”，长度为3。

用String.toCharArray()方法，将给定字符串拆成单个字符数组形式，开始遍历。
记录最长子串长度maxLength，初始值赋为0；记录当前子串列表list。
如果当前字符，不在当前子串内，将当前字符加入子串。
如果当前字符，存在当前子串内，先根据当前子串长度list.size()和maxLength的值，取其中大值，更新maxLength。然后找到上一个重复字符的index，删除子串内index位置之前的所有字符（包括index位置的字符）。最后，将当前字符加入子串。
在结束循环之后，再次检查当前子串长度list.size()和maxLength的值，取大值更新maxLength。因为可能出现最长子串是包含最后一个字符的子串。
注意检查入参。

解题代码：

 public static int lengthOfLongestSubstring(String s) {

         if (s == null) {

             throw new IllegalArgumentException("Input error");

         }

         char[] charArray = s.toCharArray();

         int maxLength = 0;

         List<Character> list = new ArrayList<>();

         for (int i = 0; i < charArray.length; i++) {

             Character c = charArray[i];

             // 判断当前字符是否重复

             if (list.contains(c)) {

                 // 更新最大长度

                 maxLength = list.size() > maxLength ? list.size() : maxLength;

                 // 删除重复之前的字符

                 int lastIndex = list.indexOf(c);

                 // lastIndex+1 代表删除次数

                 while (lastIndex + 1 > 0) {

                     list.remove(0);

                     lastIndex--;

                 }

             }

             // 当前字符是一定要加的

             list.add(c);

         }

         // 特殊情况考虑：最长字符串在原字符串尾部

         maxLength = list.size() > maxLength ? list.size() : maxLength;

         return maxLength;

     }

lengthOfLongestSubstring

秒客网

No.003：Longest Substring Without Repeating Characters

相关文章