Sliding Window

经典题目

76 Minimum Window Substring

Two pointers + Map (char array)

public String minWindow(String s, String t) {
    int[] dict = new int[128];
    for (int i = 0; i < t.length(); i++) {
        dict[t.charAt(i)] += 1;
    }
    int count = t.length();
    int start = 0, end = 0;
    int resStart = 0, resEnd = Integer.MAX_VALUE;
    char[] array = s.toCharArray();
    while (end < array.length) {
        if (dict[array[end]] > 0) {
            count -= 1;
        }
        dict[array[end]] -= 1;
        end += 1;
        while (count == 0) {
            if (end - start - 1 < resEnd - resStart) {
                resEnd = end - 1;
                resStart = start;
            }
            dict[array[start]] += 1;
            if (dict[array[start]] > 0) {
                count += 1;
            }
            start += 1;
        }
    }
    return resEnd == Integer.MAX_VALUE ? "" : s.substring(resStart, resEnd + 1);
}

340 Longest Substring with At Most K Distinct Characters

def lengthOfLongestSubstringKDistinct(self, s, k):
    """
    :type s: str
    :type k: int
    :rtype: int
    """
    count = [0] * 256
    left = 0
    right = 0
    num = 0
    ans = 0
    
    while right < len(s):
        cur = s[right]
        if count[ord(cur)] == 0:
            num += 1
        count[ord(cur)] += 1
        while num > k and left < len(s):
            count[ord(s[left])] -= 1
            if count[ord(s[left])] == 0:
                num -= 1
            left += 1
        ans = max(ans, right - left + 1)
        right += 1
    return ans

713. Subarray Product Less Than K

/*
    Method 1: Sliding Window.
    
    For each index 'right', locate the smallest index 'left' which makes a valid range.
    Then ('right' - 'left' + 1) are the number of newly found intervals.
*/

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int ans = 0;
    int left = 0;
    int cur = 1;
    
    for (int right = 0; right < nums.length; right++) {
        cur *= nums[right];
        
        while (left <= right && cur >= k) {
            cur /= nums[left];
            left++;
        }
        
        ans += right - left + 1;
    }
    
    return ans;
}