Two Pointer Problems (Part 2) - Sliding Window

Concept
209. Minimum Size Subarray Sum
713. Subarray Product Less Than K
3. Longest Substring Without Repeating Characters
438. Find All Anagrams in a String

Concept

A sliding window is a method used to solve problems on arrays by moving two pointers in the same direction. Problems of this nature don’t necessarily require a specific name; their solutions are quite natural.

Sliding window is typically an optimization of brute force solutions. The best way to master this type of problem is through practice and understanding why sliding window can be applied.

209. Minimum Size Subarray Sum

This problem is the most basic sliding window problem. We can use two pointers and to represent the left and right ends of the window, then move the pointer continuously to the right. Meanwhile, use a variable to record the sum of the interval . If meets the condition, record the difference between and as the answer, and move the pointer . Here’s the code:

class Solution {
public:
    int minSubArrayLen(int target, vector<int> &nums) {
        int l = 0, r = 0, res = INT_MAX, sum = 0;
        while (r < nums.size()) {
            sum += nums[r];
            while (sum >= target) {
                res = min(res, r - l + 1);
                sum -= nums[l];
                l++;
            }
            r++;
        }
        return res == INT_MAX ? 0 : res;
    }
};

713. Subarray Product Less Than K

The solution to this problem is very similar to the previous one, but instead of finding the length of the interval, we’re looking for the number of consecutive subintervals.

For the number of subintervals, we can observe that if is a valid window, then for must also be valid windows.

For any valid interval , the number of subsets ending at is always . Therefore, before updating each time, we add to the answer. Here’s the code:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int> &nums, int k) {
        int l = 0, r = 0, sum = 1, ans = 0;
        if (k <= 1) return 0;
        while (r < nums.size()) {
            sum *= nums[r];
            while (sum >= k) {
                sum /= nums[l];
                l++;
            }
            ans += r - l + 1;
            r++;
        }
        return ans;
    }
};

3. Longest Substring Without Repeating Characters

Unlike the previous contiguous subsequence problem, this problem requires the length of contiguous substrings. Therefore, we need to modify the condition. If duplicate characters appear within the window interval, we update . Here’s the code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0, r = 0, ans = 0;
        map<char, int> cnt;
        while (r < s.length()) {
            cnt[s[r]]++;
            while (cnt[s[r]] > 1) {
                cnt[s[l]]--;
                l++;
            }
            ans = max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
};

438. Find All Anagrams in a String

The solution to this problem is quite similar to the previous one, but instead of comparing characters, we’re comparing strings. Additionally, the length of the window in this problem remains constant, which is the length of .

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans, target(26, 0), sum(26, 0);
        if (s.length() < p.length()) return ans;
        for (int i = 0; i < p.length(); i++) target[(int) (p[i] - 'a')]++, sum[(int) (s[i] - 'a')]++;
        if (sum == target) ans.push_back(0);

        int l = 0, r = p.length();
        while (r < s.length()) {
            sum[(int) (s[l++] - 'a')]--;
            sum[(int) (s[r++] - 'a')]++;
            if (sum == target)
                ans.push_back(l);
        }
        return ans;
    }
};