2.双指针

/*
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针
若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索；
若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。
*/


//167.两数之和
/*
通过一边遍历解决在一个增序的整数数组里找到两个数，使他们的和为给定值。已知有且只有一对解。 使用遍历方向相反的指针
*/
vector<int> twoSum(vector<int>& numbers, int target) {
    int l=0, r=numbers.size()-1, sum;
    while(l<r){                     //循环条件
        sum = numbers[l] + numbers[r];
        if(sum == target) break;
        if(sum < target) l++;
        else r--;
    }
    return vector<int>{l+1,r+1};    //vector返回值写法
}


//88.合并两个有序数组
/*
给定两个有序数组，把两个数组合并为一个
两个数组长度为m，n；其中一个数组的长度被延长至m+n,多出的n用0补位，不需要开辟额外空间
题解：这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即nums1的m-1位和nums2的n-1位。
每次将较大的数字复制到nums1的后边，然后向前移动一位。因为我们也要定位这个移动的下标，所以还需要第三个指针
*/
void merge(vector<int>& nums1, int m, vector<int>&nums2, int n) {
    int pos = m-- + n-- -1;
    while(m >= 0 && n >= 0 ){
        if(nums1[m] > nums2[n])  nums[pos--] = nums1[m--];
        else nums[pos--] = nums[n--];
    }
    while(n>=0){
        nums1[pos--]=nums2[n--];
    }
}


//142.链表是否有环
/*给定一个链表，如果有环路，找出环路的开始点*，如果没有环路返回一个空指针
题解：对于链表找环路问题，有一个通用的解法---快慢指针，给定两个指针，分别命名为slow和
fast，起始位置在链表的开头。每次fast前进两步，slow前进一步，如果fast可以走到尽头，那么
说明没有环路；如果fast可以无线循环下去，那么说明一定有环路，且一定存在一个时刻slow和fast
相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并让slow和fast每次都前进
一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。
*/
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(nullptr) {} //链表初始化方法
};

//哈希表 简单粗暴 判断链表是否有环 时间空间复杂度 O(N)
ListNode *detectCycle(ListNode *head){
    unordered_set<ListNode*> visited;   //用set可以，unordered_set是哈希set，无序的速度快
    while(head != nullptr){
        if(visited.count(head)){
            return head;
        }
        visited.insert(head);
        head = head->next;
    }
    return nullptr;
}

//快慢指针方法 时间复杂度O(N) 空间复杂度O(1)
ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    //判断是否存在环路
    do{
        if(!fast || !fast->next) return nullptr;
        fast = fast->next->next;
        slow = slow->next;
    }while(fast != slow);
    //如果存在，查找环路节点
    fast = head;
    while(fast != slow){
        slow=slow->next;
        fast=fast->next;
    }
    return fast;
}


//76.最小覆盖子串(hard)
/*
题目描述：给定两个字符串S和T，求S中包含T所有字符的最短连续子字符串的长度，同时要求时间复杂度不得超过O(n)
输入输出样例：输入是两个字符串S和T，输出是一个S字符串的子串。
Input：S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
在这个样例中，S中同时包含一个A、一个B、一个C的最短子字符串是 "BANC"
题解：本题使用滑动窗口求解，即两个指针l和r都是从最左端向最右端移动，且l的位置一定在r的左边或重合。注意本题虽然在for循环里出现一个while循环，
但是因为while循环负责移动l指针，且l只会从左到右移动一次，因此总时间复杂度仍然是O(n).本题使用长度为128的数组来映射字符，也可以用哈希表来代替；
其中chars表示目前每个字符缺少的数量，flag表示每个字符是否在T中存在。
*/
string minWindow(stirng S, string T){
    vector<int> chars(128, 0);
    vector<bool> flag(128, false);
    //先统计T中的字符情况
    for(int i=0; i<T.size(); ++i){
        flag[T[i]]= true;
        ++chars[T[i]];
    }
    //移动滑动窗口，不断更改统计数据
    int cnt=0, l=0, min_l=0, min_size=S.size()+1;
    for(int r=0; r<S.size(); ++r){
        if(flag[S[r]]){
            if(--chars[S[r]] >= 0){     //因为T中可能有重复的 所用>= 而不是==
                ++cnt;
            }
            //若目前滑动窗口已包含T中全部字符，
            //则尝试将l右移，在不影响结果的情况下获得最短子字符串
            while(cnt == T.size()){
                if(r-l +1 < min_size){
                    min_l=l;
                    min_size=r-l+1;
                }
                if(flag[S[l]] && ++chars[S[l]]>0){
                    --cnt;
                }
                ++l;
            }
        }
    }
    return min_size > S.size()? "":S.substr(min_l,min_size);
}