强化4(双指针）

1. 一个数组，从两边往中间移动（对撞型）

2. 一个数组，同时向前移动（前向型）

3. 两个数组（并行型）

对撞型

• two sum类 ->灌水类

• partion类

partition

quick select -> kth largest element 第K大（比如中位数）

heap（priority queue)->前k大: O(NlogK)如果把heap size设为k的话。

top k smallest

• maxheap -cmp size k

• minheap pop k times

quick select vs quick sort

都要partition.quick select 是quick sort的一个步骤，quick select 每次都会丢一半 所以O（logn） quick sort 之后还要继续做partition操作，递归。 O（nlogn）

partition问题模板

public int partition(int[] nums, int l, int r){
    int left = l, right = r, pivot = nums[left];
    while(left < right){
        while(left < right && nums[right] >= pivot){
            right --;
        }
        nums[left] = nums[right];
        while(left < right && nums[left] <= pivot){
            left ++;
        }
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

quick sort 模板

public void sortIntegers2(int[] A) {
        quickSort(A, 0, A.length - 1);
    }

    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        int pivot = A[(start + end) / 2];

        // key point 2: every time you compare left & right, it should be 
        // left <= right not left < right
        while (left <= right) {
            // key point 3: A[left] < pivot not A[left] <= pivot
            while (left <= right && A[left] < pivot) {
                left++;
            }
            // key point 3: A[right] > pivot not A[right] >= pivot
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;

                left++;
                right--;
            }
        }

        quickSort(A, start, right);
        quickSort(A, left, end);
    }

前向型或者追击型

• 窗口类 ->子串子数组可以往窗口类想 substring，subarray

• 快慢类

窗口类 vs sliding window

sliding window 的窗口大小固定.窗口类就是找个窗口 满足某条件，窗口最大或者最小

总结固定大小的窗口：https://segmentfault.com/a/1190000012931296

固定长度模板：K-Substring with K different characters(sliding window)

for loop strs/nums长度，检测map或者数组长度，cnt ++/--

不固定长度：

窗口类的指针i,j 一直都是往前走， 都不回头，所以只遍历2n次，O（n）j永远在i前面，i在追，i,j围成窗口类。

窗口类指针移动模板

for(int i = 0; i < n; i++){
    while(j < n){
        if(条件满足){
            j++;
            更新j状态
        }else（不满足条件）{
            break;
        }   
    }
    更新i状态
}

总结

• 优化思想通过两层for循环而来

• 外层指针依然是依次遍历

• 内侧指针证明是否需要回退

Tips:

Character.isLowerCase

Character.isUpperCase

int[] copy = Arrays.copyOf(nums, n);

带map的双指针

strStr和anagrams比较：

相同点：就是len== t.length

不同点：

strStr 顺序需要，不要map。所以i,j初始就是t的间隔，每次比完一起走+

anagram 顺序不需要，所以Map

用map类就是无序，有序的话可以用2个指针各指向一个arr开始比较。

min/max substring 双指针通用模板

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.

一个map存char count。头尾指针，尾前进到满足条件，头缩进到不满足条件。2个while一个头一个尾。注意min/max的位置

模板不能做这个Longest Substring with At Least K Repeating Characters（递归）

Subarrays with K Different Integers exact = atmost(k)-atmost(k-1)

Longest Substring with At Least K Repeating Characters 不能模板

Shortest Subarray with Sum at Least K 单调栈

Longest Substring with At Most K Distinct Characters 模板

Longest Substring Without Repeating Characters

Minimum Window Substring

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }//pre临界这里，完了就被减
,map和end都要update,只有counter在if里

            while(/* counter condition */){ 

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

                if(map[s[begin++]]++ ?){ /*modify counter here*/ }//map和end都要update,只有counter在if里


            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

leetcode:

904

总结做法：

固定长度且要求顺序，可以直接str比较str，注意loop坐标的取值，不能取到尾。

固定程度不顺序的话，可以用map和count

subarray-product-less-than-k 重要结论：每加入一个新数字，多出来e-s个数组，决定于起始数字位置。unique-letter-string也用了这个结论，dp里每次多个数字，就多e-s个新数组。

Subarrays with K Different Integers：1用atmost K做:f(exactly K) = f(atMost K) - f(atMost K-1).

2达到合格K的i,j之间有x个num/char重复，res+= x+1