【C++刷题】优选算法——滑动窗口_c++ 滑窗算法题

滑动窗口算法是在可以利用单调性使用“同向双指针”来解决问题时使用。

1. 长度最小的子数组

int minSubArrayLen(int target, vector<int>& nums)
{
    size_t left = 0;
    size_t right = 0;
    long long sum = 0;
    int len = nums.size() + 1;
    while(right < nums.size())
    {
        sum += nums[right]; // 进窗口
        while (sum >= target)
        {
            // 更新结果
            if (right - left + 1 < len)
            {
                len = right - left + 1;
            }
            sum -= nums[left++]; // 出窗口
        }
        ++right;
    }
    return len == nums.size() + 1 ? 0 : len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 无重复字符的最长子串

int lengthOfLongestSubstring(string s)
{
    char arr[256];
    memset(arr, 0, 256);
    size_t len = 0;
    for(size_t left = 0, right = 0; right < s.size(); ++right)
    {
        ++arr[s[right]]; // 进窗口
        while(arr[s[right]] > 1) // 判断
        {
            --arr[s[left++]]; // 出窗口
        }
        if(right - left + 1 > len ) len = right - left + 1; // 更新结果
    }
    return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 最大连续1的个数 III

int longestOnes(vector<int>& nums, int k)
{
    size_t left = 0;
    size_t right = 0;
    size_t len = 0;
    while(right < nums.size())
    {
        if(nums[right] != 0)
        {
            if(len < right - left + 1) len = right - left + 1;
        }
        else
        {
            if(k > 0)
            {
                if(len < right - left + 1) len = right - left + 1;
                --k;
            }
            else
            {
                while (nums[left++] != 0);
            }
        }
        ++right;
    }
    return len;
}
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

4. 将 x 减到 0 的最小操作数
   转化为找出中间的一个连续的区域，使该区域的和等于整个数组的和与x的差。

int minOperations(vector<int>& nums, int x)
{
    size_t sum = 0;
    for(int e : nums) sum += e;
    x = sum - x;
    if(x == 0) return nums.size();

    size_t left = 0;
    size_t right = 0;
    sum = 0;
    size_t len = 0;
    while(right < nums.size())
    {
        sum += nums[right]; // 进窗口
        while(sum > x) // 判断
        {
            sum -= nums[left];
            ++left; // 出窗口
        }
        if(sum == x && len < right - left + 1) len = right - left + 1; // 更新结果
        ++right;
    }        
    return len == 0 ? -1 : nums.size() - len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5. 水果成篮

struct Basket
{
    int type = -1;
    int num = 0;
};

class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        size_t left = 0;
        size_t right = 0;
        int max = 0;
        Basket basket[2];
        while(right < fruits.size())
        {
            // 如果有空篮子或水果类型相同，就入窗口
            if(basket[0].type == -1 || basket[0].type == fruits[right])
            {
                basket[0].type = fruits[right];
                basket[0].num++;
                if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
            }
            else if(basket[1].type == -1 || basket[1].type == fruits[right])
            {
                basket[1].type = fruits[right];
                basket[1].num++;
                if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
            }
            else
            {
                while(true)
                {
                    if(basket[0].type == fruits[left])
                    {
                        ++left;
                        --basket[0].num;
                        if(basket[0].num == 0)
                        {
                            basket[0].type = fruits[right];
                            basket[0].num++;
                            break;
                        }
                    }
                    else if(basket[1].type == fruits[left])
                    {
                        ++left;
                        --basket[1].num;
                        if(basket[1].num == 0)
                        {
                            basket[1].type = fruits[right];
                            basket[1].num++;
                            break;
                        }
                    } 
                }
            }
            ++right;
        }
        return max;
    }
};
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
59
60
61
62

6. 找到字符串中所有字母异位词
   对于子串是否符合规则的判断，可以利用两个hash表和一个count来解决。

vector<int> findAnagrams(string s, string p)
{
    vector<int> v;
    if(s.size() < p.size()) return v;

    int count = 0; // 记录相同的有效元素的个数

    int hash_p[26];
    memset(hash_p, 0, 26 * sizeof(int));
    for(char c : p) hash_p[c - 'a']++;

    int hash_s[26];
    memset(hash_s, 0, 26 * sizeof(int));
    for(size_t i = 0; i < p.size(); ++i)
        if(hash_s[s[i] - 'a']++ < hash_p[s[i] - 'a']) ++count;

    size_t left = 0;
    size_t right = p.size() - 1;
    while(right < s.size())
    {
        if(count == p.size()) v.push_back(left);
        
        if (hash_s[s[left] - 'a']-- <= hash_p[s[left] - 'a']) --count;
        ++left;
        if(++right < s.size() && hash_s[s[right] - 'a']++ < hash_p[s[right] - 'a']) ++count;
    }
    return v;
}
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

7. 串联所有单词的子串

vector<int> findSubstring(string s, vector<string>& words)
{
    vector<int> v;
    if (s.size() < words.size() * words[0].size()) return v;

    // words的hash
    unordered_map<string, int> m_wd;
    for (string& s : words) m_wd[s]++;
    // s的hash
    unordered_map<string, int> m_s;
    // 步长step
    size_t step = words[0].size();
    // 有效元素个数count
    size_t count = 0;
    // words的单词合并长度
    size_t words_length = words.size() * words[0].size();
    // 回归坐标index
    // 只需要滑动窗口step步长次即可
    for (size_t index = 0; index < step; ++index)
    {
        m_s.clear();
        count = 0;
        for (size_t i = index, size = 0; i < s.size() && size < words.size(); i += step, ++size)
        {
            string tmp = s.substr(i, step);
            if (m_wd.count(tmp) && m_s[tmp]++ < m_wd[tmp])
            {
                ++count;
            }
        }

        size_t left = index, right = left + words_length;
        while (right <= s.size())
        {
            if (count == words.size())
            {
                v.push_back(left);
            }

            string tmp_left = s.substr(left, step);
            if (m_wd.count(tmp_left) && m_s[tmp_left]-- <= m_wd[tmp_left])
            {
                --count;
            }
            left += step;

            right += step;
            if (right <= s.size())
            {
                string tmp_right = s.substr(right - step, step);
                if (m_wd.count(tmp_right) && m_s[tmp_right]++ < m_wd[tmp_right])
                {
                    ++count;
                }
            }
        }
    }
    return v;
}
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
59

8. 最小覆盖子串

string minWindow(string s, string t)
{
    string ret = s;
    if (s.size() < t.size()) return "";

    unordered_map<char, int> t_map;
    for (char c : t) t_map[c]++;

    unordered_map<char, int> s_map;
    size_t count = 0;
    size_t left = 0, right = 0;
    while (right < s.size() && count < t.size())
    {
        if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]])
        {
            ++count;
        }
        ++right;
    }
    if (right == s.size())
    {
        if (count < t.size())
        {
            return "";
        }
        else
        {
            // 到达临界点
            while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
            {
                s_map[s[left]]--;
                ++left;
            }
            return s.substr(left, right - left);
        }
    }
    while (right < s.size())
    {
        if (count == t.size())
        {
            // 到达临界点
            while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
            {
                s_map[s[left]]--;
                ++left;
            }
            if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - left);

            // 出窗口
            s_map[s[left]]--;
            ++left;
            --count;
        }
        while (right < s.size() && count < t.size())
        {
            if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]]) // 元素存在且小于
            {
                ++count;
            }
            ++right;
        }
    }
    // 到达临界点
    while (left < right && (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]]))
    {
        s_map[s[left]]--;
        ++left;
    }
    if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - left);
    return ret;
}
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
59
60
61
62
63
64
65
66
67
68
69
70
71