滑动窗口技巧

1
2
3

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

1
2
3
4
5
6
7
8
9

int maxlen = -1;
for (int left = 0; left < S.length(); left++)
    for (int right = left + 1; right < S.length(); right++) {
     if(window[left, right) contain 重复字符) continue;
     if(right - left > maxlen) {
         maxlen = right -left;
     }
    }
return maxlen;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int left = 0, right = 0;
int maxlen = -1;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    if(window doesnot contain repeat charactor) {
        maxlen = max(maxlen, right - left);
    }

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

return maxlen;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int lengthOfLongestSubstring(string s)
{
    int maxlen = 0;
    unordered_map<char, int> window;
    int right = 0, left = 0;
    while (right < s.length())
    {
        auto rch = s[right];
        right++;
        window[rch]++;

        if (window[rch] <= 1)
        {
            maxlen = max(maxlen, right - left);
        } else {
            while (window[rch] > 1)
            {
                auto lch = s[left];
                left++;
                window[lch]--;
            }
        }
    }
    return maxlen;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// No. 76
string minWindow(string s, string t)
{
    int startId = 0;
    int rightId = 0;
    int minLen = s.length() + 1;
    int left = 0, right = 0;
    int  matchCount = 0;
    // record the only need characters
    unordered_map<char, int> window;
    unordered_map<char, int> need;

    for (auto ch : t)
        need[ch]++;

    while (right < s.length())
    {
        auto rch = s[right];
        right++;

        if (need.count(rch)) {
            // expand window
            window[rch]++;
            if (window[rch] == need[rch]) {
                matchCount++;
            }
        }

        // shrink the window
        while (matchCount == need.size())
        {
            if (right - left < minLen)
            {
                startId = left;
                rightId = right;
                minLen = right - left;
            }

            auto lch = s[left];
            if (need.count(lch)) {
                window[lch]--;
                if (window[lch] < need[lch]) {
                    matchCount--;
                }
            }
            left++;
        }
    }

    return rightId - startId > 0 ? s.substr(startId, rightId - startId) : "";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLen = 0;
        int left = 0, right = 0;
        unordered_map<char, int> window;
        while (right < s.length()) {
            auto rch = s[right];
            window[rch]++;
            right++;

            // find max count char
            int maxCount = -1;
            for (auto iter = window.begin(); iter != window.end(); iter++) {
                maxCount = max(maxCount, iter->second);
            }

            if (maxCount + k >= right - left) {
                maxLen = max(right - left, maxLen);
            } else {
                auto lch = s[left];
                window[lch]--;
                left++;
            }
        }

        return maxLen;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int maxLen = 0;
        int left = 0, right = 0;
        unordered_map<int, int> window;
        while (right < A.size()) {
            auto rnum = A[right];
            window[rnum]++;
            right++;

            if (window[1] + K >= right - left) {
                maxLen = max(right - left, maxLen);
            } else {
                auto lnum = A[left];
                window[lnum]--;
                left++;
            }
        }

        return maxLen;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

int subarraysWithKDistinct(vector<int>& A, int K) {
        int left = 0, right = 0;
        unordered_map<int, int> window;

        int count = 0;
        while (right < A.size()) {
            auto rnum = A[right];
            window[rnum]++;
            right++;

			// 如果当前的窗口中超过了K个不同的整数，那么需要缩小左边缘（即窗口左移）
            while (window.size() > K) {
                auto lnum = A[left];
                window[lnum]--;
                if (window[lnum] == 0) {
                    window.erase(lnum);
                }
                left++;
            }

            // 当前的窗口有K个不同的整数，移动左边缘，遍历所有满足条件的窗口
            if (window.size() == K) {
                unordered_map<int, int> subWindow(window);
                int tmpLeft = left;

                while (subWindow.size() == K) {
                    count++;
                    subWindow[A[tmpLeft]]--;
                    if (subWindow[A[tmpLeft]] == 0) {
                        subWindow.erase(A[tmpLeft]);
                    }
                    tmpLeft++;
                }
            }
        }

        return count;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int subarraysWithKDistinct(vector<int>& A, int K) {
        int left = 0, right = 0;
        unordered_map<int, int> window;
        int count = 0;
        while (right < A.size()) {
            auto rnum = A[right];
            window[rnum]++;
            right++;

            while (window.size() > K) {
                auto lnum = A[left];
                window[lnum]--;
                if (window[lnum] == 0) {
                    window.erase(lnum);
                }
                left++;
            }


            int tmpLeft = left;
            while (window.size() == K) {
                count++;
                window[A[tmpLeft]]--;
                if (window[A[tmpLeft]] == 0) {
                    window.erase(A[tmpLeft]);
                }
                tmpLeft++;
            }
            // recover the window
            while (tmpLeft > left) {
                window[A[tmpLeft-1]]++;
                tmpLeft--;
            }
        }
        return count;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// C++ program to demonstrate functionality of unordered_map
#include <iostream>
#include <unordered_map>  //
using namespace std;

int main()
{
	// Declaring umap to be of <string, int> type
	// key will be of string type and mapped value will
	// be of double type
	unordered_map<string, int> umap;

	// inserting values by using [] operator
	umap["GeeksforGeeks"] = 10;
	umap["Practice"] = 20;
	umap["Contribute"] = 30;

	// Traversing an unordered map
	for (auto x : umap)
	cout << x.first << " " << x.second << endl;

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// C++ program to demonstrate functionality of unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    // Declaring umap to be of <string, double> type
    // key will be of string type and mapped value will
    // be of double type
    unordered_map<string, double> umap;

    // 新增键值对
    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap["root3"] = 1.732;
    umap["log10"] = 2.302;
    umap["loge"] = 1.0;

    // 插入键值对，可以使用c++的make_pair函数
    umap.insert(make_pair("e", 2.718));

    string key = "PI";

    // 查询方法一
    if (umap.find(key) == umap.end())
        cout << key << " not found\n\n";

    // If key found then iterator to that key is returned
    else
        cout << "Found " << key << "\n\n";

    // 查询方法二
    if (umap.count(key) == 0 )
        cout << key << " not found\n\n";

    // If key found then iterator to that key is returned
    else
        cout << "Found " << key << "\n\n";

    // 遍历方法一
    unordered_map<string, double>::iterator itr;
    cout << "\nAll Elements : \n";
    for (itr = umap.begin(); itr != umap.end(); itr++)
    {
        // itr works as a pointer to pair<string, double>
        // type itr->first stores the key part and
        // itr->second stroes the value part
        cout << itr->first << " " << itr->second << endl;
    }

    // 遍历方法二
    for (auto iter : umap) {
        cout << iter.first << " " << iter.second << endl;
    }

    return 0;
}

1
2
3
4
5

if (umap[key] > 0) {
    cout << key << " is found\n";
} else {
    cout << "Not found\n";
}