Leetcode992: K 个不同整数的子数组

【题目描述】
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

【思路】
关键词： 滑动窗口，双指针

1. right指针一直向右，直到match = K
2. 临时的移动left，到match<K
   match = K时都要记录一次结果
3. 记录完了，left没变，继续移动right
4. 当match>k时才是要移动left改变窗口大小的时候

【坑】

1. 临时的left使用（想不到），记录完结果之后hashmap里面的key和value要恢复
2. 临时的left 和临时diff
3. 更新的顺序要注意，因更新顺序写错导致有bug

【code】

int subarraysWithKDistinct(vector<int>& A, int K) {
    if (A.size() == 0) return 0;
    if (K > A.size()) return 0;
    int left = 0;
    int right = 0;
    int diffNum = 0;
    int res = 0;
    vector<int> path;
    unordered_map<int, int> map;
    while (right != A.size()) {
        cout << "---- -- -- ---new move right --- --- --- --" <<endl;
        cout << "right: " << right << endl;
        cout << "left: " << left << endl;
        cout << "diffNum: " << diffNum << endl;
        if (map[A[right]] == 0) diffNum++;
        map[A[right]]++;
        cout << "map right: " << A[right] << " : " << map[A[right]] << endl;
        cout << "-------------------------" << endl;
        right++;


        while (diffNum > K) { //真正地缩小窗口
            if (map[A[left]] == 1) diffNum--;
            map[A[left]]--;
            left++;
        }
        int tmp = left;
        int tmpDiff = diffNum; //临时值的位置
        while ((tmpDiff == K)&&(tmp<=right)) { // 等于K时 左移left统计结果
            //注意这里移的只是临时值，实际上left没有移动
            cout << "diffNum = K" << endl;
            cout << "map: " << A[tmp] << " " << map[A[tmp]] << endl;
            res++;
            if (map[A[tmp]] == 1) tmpDiff--;  //diff也要用临时值
            map[A[tmp]]--;  //这里顺序错了
            tmp++;
        }

        //恢复结果
        while (tmp > left) {
            map[A[tmp - 1]]++;
            tmp--;
        }
    }
    return res;
    
}