无重复字符最长子串问题

描述(滑动窗口的应用)

1.给定任意一个字符串，找出不含重复字符的最长子串，返回其长度。

题解

public int maxLengthOfSubStr(String str) {
  //时间复杂度：O(N)
  if (null == str || str.length() == 0) {
      return 0;
  }
  //左下标
  int leftIndex = 0;
  //最大不重复子串的长度(左右下标的差值)
  int maxLength = 0;
  //以字符为key，字符对应的下标index为value建立hash表
  Map<Character, Integer> map = new HashMap<>();
  for (int rightIndex = 0; rightIndex < str.length(); rightIndex++) {
        if (map.containsKey(str.charAt(rightIndex))) {
            leftIndex = Math.max(leftIndex, map.get(str.charAt(rightIndex)) + 1);
        }
        map.put(str.charAt(rightIndex), rightIndex);
        maxLength = Math.max(maxLength, rightIndex - leftIndex + 1);
  }
  return maxLength;
}

分析

1.假设所给定的字符串都不重复如：abcdefgh，要求最大子串其实就是本身的长度length代入题目当中也就是length = rightIndex - leftIndex + 1。这是理想情况。
2.如果重复的是连续两个字符如：abbc，首先leftIndex = 0，当遍历到第二个b时，此时会首先在map中查找，因为map已经包含了第一个b并且对应的下标值为1。这里注意，稍后解释为什么要map.get(str.chatrAt(rightIndex)) + 1。
3.既然是滑动窗口法，上述分析了，如果理想状态，那么这个窗口是一直增长的，直到等于str的length。那么如果重复的话(首先分析连续重复)，拿abbc举例，第二个b进入时，此时重复了，窗口应该去掉一截，也就是leftIndex需要增大，换句话说：当遇到有重复的情况，我们的窗口是在变小的。并且leftIndex会跳过重复的字符而从下一位开始。对于abbc中map.get(str.chatrAt(rightIndex))，第一个b的下标为1，遍历到第二个b时，此时map.get(str.chatrAt(rightIndex)) + 1 = 2 = leftIndex。窗口的起点变为第二个b。
4.如果字符串为abca，这个就比较更好理解，当遍历到第二个a时，因为重复，而map中包含a并且map.get('a') = 0，第二个a进入窗口，第一个a要被截去。所以：leftIndex = map.get('a') + 1 = 1，窗口的起点从b开始，以此。