1/22-23，two pointers - forward(前向型)

类型：remove duplicate elements / sliding windows

Remove Duplicates from Sorted Array

前向型

two pointers高频。

使用两个指针，一个迭代数组判断重复，另一个length是新数组的指针，表示长度。length应停在重复的数字上，并随着循环被重置成当前不是重复的数字。注意前提，array已经sorted, 需要clarification.

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[index] != nums[i]) {
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }
}

Remove Duplicates from Sorted Array II

类似上题，新数组可以出现重复，但不能超过指定重复的次数，同时返回的也是新数组的长度。

1/10重写了这段，套用+简化了I的模板。当检查到了第一次重复时，length指针仍然可以右移1位。

如果要求重复的次数小于等于k，只要把if (count < 2) 改成 count < k 即可。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int count = 1, index = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[index]) {
                nums[++index] = nums[i];
                count = 1;
            } else if (count < 2) {
                nums[++index] = nums[i];
                count++;
            } 
        }
        return index + 1;
    }
}

Remove Element

two pointer高频，要in place remove指定的数，返回新数组的长度。

思路是用一个指针i迭代数组，另一个length表示新数组的长度，这点和上面的remove dup I一样，都是为了看length能走到哪。当遍历的数不是要删的数时，length+1，同时update。如果是要删的数，就不增加length。

// time: O(n) but need copy numbers when target numbers are rare...
public int removeElement(int[] nums, int val) {
    if (nums == null || nums.length == 0) return 0;
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[index++] = nums[i]; 
        }
    }
    return index;
}




// time: O(n)    
// another solution is more suitable to the situation like the elements to remove are rare..
public int removeElement2(int[] nums, int val) {
    if (nums == null || nums.length == 0) return 0;

    int index = nums.length - 1, cur = 0;
    while (cur <= index) {
        if (nums[cur] == val) {
            nums[cur] = nums[index--];
        }
        else {
            cur++;
        }
    }
    return cur;
}

length的初始值设为0，因为可能数组的数全部都是要删掉的数。把这题和remove dup I类比起来记一下。

1/10更新后，上面三道题的思路做法基本一样。

2/23 补充，

如果不是in place，可以利用hash table或set。所以这里是一个clarification point。

12/11复习总结

对于remove题型的归类，首先通常都要求in-place操作，因为如果让新建一个array的话，那就简单了。

删除分两类，要不就是删除重复的，要不就是删除指定的。length指针停在要删除的位置，等待重置。

归纳解题的方法：in-place用到two pointers，一个用来check重复，一个停在要重置的重复数字上，同时表示新数组长度。

在一次遍历中，如果该元素不满足要删除的条件(不是重复的，或者不是要删的)，那就可以移动长度指针。如果该元素满足删除条件，长度指针就停留，等另一指针check到下个不满足删除条件的元素时，再把长度指针所指的那个数赋成当前不用删除的那个元素。

sliding window

Longest Substring Without Repeating Characters

用一个left pointer记录合法的左边界位置，一个变量存当前的max length subarray，一个hashtable记录访问过的char和index。

"the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string, and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward."

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;

        int start = 0, len = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c) + 1);
            }
            map.put(c, i);
            len = Math.max(len, i - start + 1);
        }
        return len;
    }
}

容易忽视的细节是要注意什么时候才能更新left pointer: 当前的char重复了，但合法的左边界一定不能回到之前的左边。

例如，对于‘abcdbeam’，在指针i指向第二个‘b’时，left pointer变为指向'c'，然后当i指向第二个'a'时，如果此时left pointer再指向第一个‘b’，范围反而扩大就错了。

利用前向型解题模板，时间复杂度O(n)。

,,,

Longest Substring with at most 2 distinct Characters

note that, as usual, use two pointers to represent the sliding window, and in this problem, we should discuss the length of the map.

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) return 0;

        int start = 0, len = 0;
        Map<Character, Integer> map = new HashMap<>();  // store the value count pair
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);

            while (map.size() > 2) {
                char old = s.charAt(start);
                map.put(old, map.get(old) - 1);
                if (map.get(old) == 0) {
                    map.remove(old);
                }
                start++;
            }
            len = Math.max(len, i - start + 1);
        }
        return len;
    }
}

Longest Substring with At Most K Distinct Characters

This problem can be solved using two pointers. The important part is while loop, we move left pointer to make sure the map size is less or equal to k. This can be easily extended to any number of unique characters.

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) return 0;

        Map<Character, Integer> map = new HashMap<>(); // key: char, value: freq
        int n = s.length();
        int maxLen = 0;
        int left = 0; 
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);

            map.put(c, map.getOrDefault(c, 0) + 1);
            while (map.size() > k) {      // pay attention: this is general template, can be extend to 2,3,..
                char tmp = s.charAt(left);
                int freq = map.get(tmp);
                if (freq == 1) {
                    map.remove(tmp);
                } else {
                    map.put(tmp, freq - 1);
                }
                left++;
            }
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }
}

Minimum Size Subarray Sum

和前一题一个思路，时间复杂度O(n).

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int left = 0, len = Integer.MAX_VALUE, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];

            while (sum >= s) {        // pay attention: 如果满足条件，不断move left
                len = Math.max(len, i - left + 1);
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

Minimum Window Substring

hard 题，但是思路是一样的，还是只用一个hashmap，然后遍历string s

use another count to record how many distinct letters in the original array instead of remove the entry in the map.
use another index to record the start point when we found the minimum window substring...

class Solution {
    public String minWindow(String s, String t) {
        if (s == null) return "";

        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int left = 0, count = map.size();  
        int index = 0, len = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    count--;
                }

                while (count == 0) {
                    if (len > (i + 1) - left) {
                        len = (i + 1) - left;
                        index = left;
                    }
                    char tmp = s.charAt(left);
                    if (map.containsKey(tmp)) {
                        map.put(tmp, map.get(tmp) + 1);
                        if (map.get(tmp) > 0) {
                            count++;
                        }
                    }
                    left++;
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(index, index + len);
    }
}

Sliding Window Maximum

妙：用deque数据结构（实际上采用LinkedList的形式）来做一个`递减的queue`.

the idea behind it: 维持monotonuous queue: one end is always at max and the other end is min. Always need to return the max end of queue.

when adding new elements x: start from small-end of the queue, drop all smaller elements and append to first element larger than x.
when sliding window: queue curr window 里面最大的已经在max-end, remove it if needed.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;

        int[] rst = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();   // queue...  or use new ArrayDeque<>()   just similar to maxheap
        for (int i = 0; i < k - 1; ++i) {
            // add first k items
            inQueue(deque, nums[i]);
        }

        for (int i = k - 1; i < n; ++i) {
            inQueue(deque, nums[i]);   // add to maxHeap, if aplicable
            rst[i - k + 1] = deque.peekFirst();
            outQueue(deque, nums[i - k + 1]); // remove top max if the num == max
        }
        return rst;
    }

    private void inQueue(Deque<Integer> deque, int num) {
        while (!deque.isEmpty() && deque.peekLast() < num) {
            deque.pollLast();
        }
        deque.offerLast(num);
    }

    private void outQueue(Deque<Integer> deque, int num) {
        if (deque.peekFirst() == num) {
            deque.pollFirst();
        }
    }
}

two pointers - forward