滑动窗口

滑动窗口

leetCode 第3题 无重复字符的最长子串长度

在字符串中找到不重复字符的最长子串长度。

保证当前窗口的子串都是无重复的。

使用一个set来存放无重复的子串，在遍历模式串的过程中，如果下一个字符在set中存在，则说明出现重复字符了，此时将记录子串开始下标的指针后移，直到不会出现重复字符为止，在每次遍历结束后，都更新最长长度。

public int lengthOfLongestSubstring(String s) {
  // 空字符串判断
  if (s.length() == 0) return 0;
  // 定义存放最长子串的set集合
  Set<Character> set = new HashSet<>();
  // 最大长度
  int maxLength = 0;
  // 指向子串开始字符的索引
  int left = 0;
  // 指向子串结束字符的索引
  int right = 0;
  // 循环结束条件，right到达字符串结尾
  while (right < s.length()) {
    // 如果set中不存在字符，则让right后移
    if (! set.contains(s.charAt(right))) {
      set.add(s.charAt(right++));
    } else {
      // 如果存在，right不动，排除掉与right所指向字符相同的字符
      set.remove(s.charAt(left++));
    }
    // 每次结束都更新最大长度
    maxLength = Math.max(set.size(), maxLength);
  }
  return maxLength;
}

leetCode 第567题 字符串排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

例如： s1: “ab” s2: “eidbaooo” 则返回true， ab的排列之一ba是s2的子串。

1. 遍历子串s1，用一个数组word存放s1中每个字符的个数；
2. 遍历模式串s2，在遍历的过程中，去word数组中消耗一个当前遍历的字符，则让word[当前字符-‘a’] –;
3. 如果在数组中不存在s2中的字符，则通过当前字符去数组拿的值肯定是小于0的，则往数组中补当前字符。并让另一个指针后移；
4. 最后判断当前两个指针所指子串的长度是否与s1相等。相等则返回true。

总结： 第一步先获取到s1中每个字符的个数，第二步遍历s2，i指向遍历过程中的当前字符，而j指向的是在s2中存在s1的字符的开始位置。其实就是在遍历s2的过程中，把每一个字符拿出来去s1中看看，有没有这个字符，有的话就说明匹配到了，让i++。直到匹配成功，如果没拿到，则说明当前字符不存在于s1中，则让j后移

public boolean checkInclusion(String s1, String s2) {
        int[] word = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            // 储存字串字母的个数
            word[s1.charAt(i) - 'a'] ++;
        }
  // 遍历s2, i指向当前遍历的字符，j指向s2中存在s1字符的开始位置
        for(int i = 0, j = 0; i < s2.length(); i ++) {
            // 从word里面消耗一个字母
            word[s2.charAt(i) - 'a'] --;
            // 如果字串中没有该字符，则补充字符，让j++
            while (word[s2.charAt(i) - 'a'] < 0) {
                word[s2.charAt(j) - 'a'] ++;
                j ++;
            }

            if (i - j + 1 == s1.length()) 
                return true;
        }
        return false;
}