LeetCode： 3 无重复字符的最长子串（Java）

3. 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

最初始的解法方法就是遍历暴力每个元素，然后以那个元素为起始点，然后进行判断是否出现了重复元素，这样时间的复杂度就是O(n2)，这样的时间复杂度有点高，基本上已经预定了时间超出限制。所以我们要用别的解法方法。
那么比较好的解决方法就是用双指针的思想，这题其实把握了思想还是挺简单的，要保证无重复的的，一般会先想到HashSet，可以保证数组的字符的唯一性。
设置一左一右两个指针，每次我们都移动右指针，如果右边的指针中的元素在Set中存在了，那么就要开始根据已经存在的元素移动左边指针了。同时我们要把左右指针里面的元素所在的索引值（index）给保存下来。
代码还是很好理解的：

ｓｈｏｗ　ｔｈｅ　ｃｏｄｅ

 public int lengthOfLongestSubstring(String s) {

     if (s.length() == 0) return 0;

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

     LinkedList<Integer> list = new LinkedList<>();

     char[] charsArray = s.toCharArray();

     int left = 0;

     int res = 0;

     for (int right = 0, len = charsArray.length; right < len; ++right) {

         if (set.contains(charsArray[right])) {

             res = Math.max(res, right - left);

             while (set.contains(charsArray[right])) {

                 int index = list.removeFirst();

                 set.remove(charsArray[index]);

             }

             list.addLast(right);

             left = list.getFirst();

             set.add(charsArray[right]);

         } else if (right == len - 1) {

             res = Math.max(res, right - left + 1);

         } else {

             set.add(charsArray[right]);

             list.addLast(right);

         }

     }

     return res;

 }

时间复杂度O(n)，空间复杂度O(n)。

巴特西

LeetCode： 3 无重复字符的最长子串（Java）

3. 无重复字符的最长子串

最新文章

热门文章

巴特西

LeetCode： 3 无重复字符的最长子串 （Java）

3. 无重复字符的最长子串

最新文章

热门文章

LeetCode： 3 无重复字符的最长子串（Java）