about Sliding Window1

Wed, Sep 1, 2021 9-minute read

Sliding Window pattern in algorithm, 滑动窗口套路

Substrings of Size Three with Distinct Characters
Longest Substring Without Repeating Characters
Minimum Window Substring
Contains Duplicate
Contains Duplicate II
Contains Duplicate III
水果成篮

滑动窗口更多处理连续问题， “Longest Substring“， ”Subarray“

Substrings of Size Three with Distinct Characters

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length three in s.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

class Solution {
    public int countGoodSubstrings(String s) {
      int count = 0;
    
     for (int i = 0, j = 1; j < s.length(); j++) {
         if (s.charAt(j) == s.charAt(j - 1)) {
             i = j;
         }
         if (j - i == 2) {
             count += s.charAt(j) != s.charAt(i++) ? 1 : 0;
         }
     }
    return count;
    }
}

Input: s = “aababcabc” Output: 4

 public int numberOfSubstrings(String s) {
 3         int len = s.length();
 4         int[] letter = new int[3];
 5         int count = 0;
 6         int res = 0;
 7         int start = 0;
 8         int end = 0;
 9         while (end < s.length()) {
10             char c1 = s.charAt(end);
11             if (letter[c1 - 'a']++ == 0) {
12                 count++;
13             }
14             while (count == 3) {
15                 res += len - end;
16                 char c2 = s.charAt(start);
17                 if (letter[c2 - 'a']-- == 1) {
18                     count--;
19                 }
20                 start++;
21             }
22             end++;
23         }
24         return res;
25     }

Longest Substring Without Repeating Characters

leetcode

the input are ascii, there are only 128 unique characters => max length = 128

ASCII 码中，一个英文字母（不分大小写）为一个字节，一个中文汉字为两个字节。

On²能做到 10^8 10^9 次方了不起了

Given a string s, find the length of the longest substring without repeating characters.


Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

没有重复字母，右移动，有，左移动

set

p w w i r set.remove , i++ -> 直到 set 里面没有重复元素

class   Solution() {
    public int lengthOfLongestSubstring (String s) {
        int res = 0;
        Set<Character> set = new HashSet<>();
        for (int left = 0, right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            int tmp = right - left + 1;
            right++;
            res = Math.max(res, tmp);
        }
        return res;
    }
}

map: 找到重复的元素的下标，上面的解法已经显著提升了效率，当然还有进一步优化的空间。left 需要移动的位置其实不需要逐个遍历，当 s.charAt(right)重复时，left 的位置应该是 right + 1。使用 map 记录下 char 和 index 的对应位置就能够直接使用

p w w p l r left = Math.max(left, map.get(s.charAt(right)) + 1):

这里没有直接用 left = map.get(s.charAt(right)) + 1

p   w   w   p   e   w
l
r       

map{(p, 1)}; 

r++; res = 1;

p   w   w   p   e   w
l
    r       

map{(p, 1), (w, 2)};

r++; res = 2;

p   w   w   p
        l           
        r

l = map.get(s.charAt(right)) = 2

map{(p, 1), (w, 3)};


p   w   w   p
        l            
            r

left = Math.max(left, map.get(s.charAt(right)) );

直接造成了 left 左移

map 里面映射的是 R 出现的后一位，

tmsmfdut

我经常纠结要不要前置处理 R，实际上如果映射坐标，是不能前置处理 R 的，比如下面频率这道，因为 R 在 t, m s 的时候，如果我们让 R 移到 m, map 里面映射了 R 的坐标，这时候 L 其实需要跳到 s 位置，而不是 m 的位置，如果 R 在 s 的时候，我们先判断 map 里面是不是已经有 m 了，如果有了让 L 跳到此时 R 坐标，s 位置，然后让 R++， map.put R 坐标就是第二个 m 的位置才是对的。

class   Solution() {
    public int lengthOfLongestSubstring (String s) {
       if (s.length() == 0) {
            return 0;
        }
        
        int L = 0, R = 0, len = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (R < s.length()) {
            char ch = s.charAt(R);
            if (map.containsKey(ch)) {
                // map已经有的ch位置的后一位
                L = Math.max(L, map.get(ch) + 1);
            }
            
            len = Math.max(len, R - L + 1);
            map.put(ch, R++);
        }
        return len;
}
}

map 里面映射的是出现的频率

 int res = 0;
Map<Character, Integer> map = new HashMap<>();

for (int fast = 0, slow = 0; fast < s.length(); fast++) {
    char right = s.charAt(fast);
    map.put(right, map.getOrDefault(right, 0) + 1);
    while (map.get(right) > 1) {
        char left = s.charAt(slow);
        map.put(left, map.get(left) - 1);
        slow++;
    }
    res = Math.max(res, fast - slow + 1);
}
return res;
}
}

因为本题设定的字符范围有限，可以使用定长的数组代替 map，来追求更高的性能。

最巧妙的是 if (map[c] >= left) 不仅替代了 map.containsKey，也解决了 left 可能在前面出现过的问题（left 没出现和在前面出现在这里一样）。 abba arr[a] = 0, arr[b] = 1, arr[b]

    	if (s.length() == 0)
		return 0;
	int[] map = new int[128];
	Arrays.fill(map, -1);

	int res = 0, left = 0;

	for (int i = 0; i < s.length(); i++) {
		char c = s.charAt(i);
		if (map[c] >= left)
			left = map[s.charAt(i)] + 1;
		map[c] = i;
		res = Math.max(res, i - left);
	}

	return res + 1;
    } // Runtime: 3 ms,

Minimum Window Substring

leet

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.
Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:

hashmap: <a, 1> <b, 1> <c, 1>

<a, 0> <b, 0> <c, 0> 说明条件符合，移动 left，直到 0 变成 1，继续移动 right

class Solution {
    public String minWindow(String s, Stirng t) {
        // Assumption: s, t are both not null

      // Assumption: s, t are both not null

      
          // corner case
        if (s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> wordDict =constructWordDict(t);
        int slow = 0, minLen = Integer.MAX_VALUE, matchCount = 0, index = 0;
        for (int fast = 0; fast < s.length(); fast++) {
         char ch = s.charAt(fast);
         Integer count = wordDict.get(ch);
         // 如何不再，直接忽略继续下去
         if (count == null) {
             continue;
         }
         wordDict.put(ch, count - 1);
          if (count == 1) {
            matchCount++;
         }
         while (matchCount == wordDict.size()) {
             // 找到了
             if (fast - slow + 1 < minLen) {
                 minLen = fast - slow + 1;
                 index = slow;
             }
             char leftmost = s.charAt(slow++);
             Integer leftmostCount = wordDict.get(leftmost);
             if (leftmostCount == null) {
                 continue;
             }
             wordDict.put(leftmost, leftmostCount + 1);
              if (leftmostCount == 0) {
                 matchCount--;
             }
         }
        
    }
     return minLen == Integer.MAX_VALUE ? "" : s.substring(index, index + minLen);
    }

    private Map<Character, Integer> constructWordDict(String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : t.toCharArray()) {
            Integer count = map.getOrDefault(ch, 0);
            map.put(ch, count + 1);
        }
        return map;
    }
    // s = "abbc" , map = {'a': 1, 'b': 2, 'c': 1,}
}

  int[] arr = new int[128];
        
    char[] s_arr = s.toCharArray();
    char[] t_arr = t.toCharArray();
        
    for (char ch : t_arr){
        arr[ch]++;
    }
     
    int slow = 0, fast = 0; 
    int len = Integer.MAX_VALUE;
    int count = 0, index = 0;
    while (fast < s_arr.length) {
        char cur = s_arr[fast];
        if (--arr[cur] >= 0) {
            count++;
        }
        while (count == t_arr.length) {
            if (len > fast - slow + 1) {
                len = fast - slow + 1;
                index = slow;
            }
            char slowChar = s_arr[slow];
            if (++arr[slowChar] > 0) {
                count--;
            }
            slow++;
        }
        fast++;
    }
     
     return len == Integer.MAX_VALUE ? "" : s.substring(index, index + len); 
    }

Contains Duplicate

leetcode

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

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

        for (int fast = 0; fast < nums.length; fast++) {
            if (set.contains(nums[fast])) {
                return true;
            }
           
            set.add(nums[fast]);
             if (set.size() > k) {
                set.remove(nums[fast - k]);
            }
        }
        return false;
    }

public class Solution {
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i= 0; i < nums.length; i++) {
      if (i > k) {
        set.remove(nums[i- k - 1]);
      }
      if (!set.add(nums[i])) {
        return true;
      }
    }
    return false;
  }
}

public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	
	for(int i = 0; i <  nums.length; i++) {
		Integer ord = map.put(nums[i], i);
		if(ord != null && i - ord <= k) {
			return true;
		}
	}
	
	return false;
}

Contains Duplicate III

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

public class Solution {
 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Long> treeSet = new TreeSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            Long n = nums[i] * 1L;
            Long L = treeSet.floor(n);
            Long R = treeSet.ceiling(n);
            if (L !=  null && n - L <= t) return true;
             if (R != null && R - n <= t) return true;
            treeSet.add(n);
            if (i >= k) {
                treeSet.remove(nums[i - k] * 1L);
            }
        }
        return false;    
}

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < Math.min(nums.length, i + k + 1); j++) {
                if (nums[i] > 0 && nums[j] < 0 || nums[i] < 0 && nums[j] > 0) {
                    if (Math.abs(nums[i]) - t > 0 
                        || Math.abs(nums[i]) - t + Math.abs(nums[j]) > 0) {
                        continue;
                    }
                }
                
                if (Math.abs(nums[i] - nums[j]) <= t) {
                    return true;
                }
            }
        }
                    
        return false;
    }

水果成篮

leetcode

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组fruits表示，其中 fruits[i] 是第i棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

这个就是固定距离的窗口，里面有个过程，我习惯先判断 left，这里是右边先放入 map，对比前面几道 while（left 如何），这里应该是固定长度的关系，所以先放入右边。这里不是无重复，所以 map 不要用映射坐标的方法。

public int totalFruit(int[] fruits) {
if(fruits == null || fruits.length == 0) return 0;
         
         int left = 0;
         int right = 0;
         HashMap<Integer, Integer> map = new HashMap<>();
         int max = 1;
         
         while(right < fruits.length){
              map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
             while(left < right && map.size() > 2){
                 map.put(fruits[left], map.get(fruits[left]) - 1);
                 if(map.get(fruits[left]) == 0) map.remove(fruits[left]);
                 left++;
             }
           
             max = Math.max(max, right - left + 1); // + 1 is for 0 - based indexing
             right++;
         }
         return max;
    
    }

 int len = fruits.length;
        int left = 0;
        int right = 0;
        int res = 0;
        int[] map = new int[100001];
        int count = 0;
        while (right < len) {
            if (map[fruits[right]] == 0) {
                count++;
            }
            map[fruits[right]]++;
            while (count > 2) {
                res = Math.max(res, right - left);
                map[fruits[left]]--;
                if (map[fruits[left]] == 0) {
                    count--;
                }
                left++;
            }
            right++;
        }
        res = Math.max(res, right - left);
        return res;

这里注意 map.remove 用法

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/MPnaiL

感谢：她们都有题库在 github 上直接有，都是大神, 都富有详细解法，对新人特别适合了解解题思路

https://leetcode-cn.com/problems/wtcaE1/solution/jian-dan-yi-dong-javac-pythonjshua-dong-dtang/
宫水三叶
Grandyang (https://www.cnblogs.com/grandyang/)

I'm Riley Shen