Two Pointers - 前向型指针summary

这类题中，Brute Force是扫两次，On2的复杂度。而Brute Force重复计算了元素，所以可以用Two Pointers来优化。

Minimum Size Subarray Sum:

int minimumSize(vector<int> &nums, int s) {
        // write your code here
        if(nums.empty()) return s == 0 ? 0 : -1;
        int start = 0, min_len = nums.size()+1;
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            while(sum >= s){
                min_len = min(min_len, i-start+1);
                sum -= nums[start++];
            }
        }
        return min_len == nums.size() + 1 ? -1 : min_len;
    }

Longest Substring Without Repeating Characters:

int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        unordered_map<char, int> mp;
        int start = 0, max_len = 0;
        for(int i=0; i<s.length(); i++){
            if(mp.count(s[i])){
                start = max(start, mp[s[i]] + 1);
            }
            mp[s[i]] = i;
            max_len = max(max_len, i-start+1);
        }
        return max_len;
    }

Longest Substring with At Most K Distinct Characters:

int lengthOfLongestSubstringKDistinct(string s, int k) {
        // write your code here
        if(s.empty() || k <= 0) return 0;
        int start = 0, max_len = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<s.length(); i++){
            mp[s[i]]++;
            while(mp.size() > k){
                if(--mp[s[start]] == 0) mp.erase(s[start]);
                start++;
            }
            max_len = max(max_len, i-start+1);
        }
        return max_len;
    }

Minimum Window Substring:

string minWindow(string &source, string &target) {
        // write your code here
        unordered_map<char, int> mp;
        for(int i=0; i<target.length(); i++){
            mp[target[i]]++;
        }
        int cnt = 0, left = 0;
        int min_len = INT_MAX, minLeft = 0;
        
        for(int i=0; i<source.length(); i++){
            if(mp.count(source[i])){
                mp[source[i]]--;
                if(mp[source[i]] >= 0) cnt++;
            }
            while(cnt == target.length()){
                if(i-left+1 < min_len){
                    min_len = i-left+1;
                    minLeft = left;
                }
                if(mp.count(source[left])){
                    mp[source[left]]++;
                    if(mp[source[left]] > 0) cnt--;
                }
                left++;
            }
        }
        return min_len == INT_MAX ? "" : source.substr(minLeft, min_len);
    }