无重复字符的最长子串

算法题解：无重复字符的最长子串

leetcode地址： leetcode

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

示例 1:

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

解法1：暴力求解

• 思路：遍历字符串，以每一个字符作为子串的起始字符，向后查找直到遇到和该字符相同的字符，记录长度，依次执行直到找到最长长度。

• 题解如下：

   public int maxIndexStrLength(String s) {
     int maxLength = 0;
     for (int index = 0; index < s.length(); index++) {
  
         int length = 1;
         int i = index + 1;
         for (; ; ) {
             if (i >= s.length()) {
                 break;
             }
             String ts = s.substring(index, i);
             char c = s.charAt(i);
             if (ts.contains(c + "")) {
                 break;
             }
             length++;
             i++;
         }
         maxLength = maxLength > length ? maxLength : length;
     }
     return maxLength;
  }

解法2：滑动窗口法

• 思路：在使用暴力解法时我们会发现实际上对于无重复子串来讲，我们产生了一些冗余的判断操作。例如对于串sdabcabcbb，判断了子串sdabc之后，当后面再出现字符a，那么重复字符之前的串直接舍弃就好。即直接从bca…开始判断即可。这样可以减少大量的不必要的判断与计算操作。
• 题解如下：

public int maxIndexStrLength(String s) {
  HashMap<Character, Integer> map = new HashMap<>();
  int start = 0, max = 0;

  for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      //如果当前元素与滑动窗口中的元素重复：
      if (map.containsKey(c) && map.get(c) >= start) {
          max = Math.max(max, i - start);
          start = map.get(c) + 1;
          //如果当前元素与滑动窗口中的元素不重复，但已经遍历到了最后一个字符：
      } else if (i == s.length() - 1) {
          max = Math.max(max, i - start + 1);
      }
      map.put(c, i);
  }
  return max;
}

总结

• 滑动窗口法的思路可以用来解决很多字符串相关的问题