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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = 0x3f3f3f3f;
        int sum = 0;
        int l = 0, r = 0;
        int n = nums.size();
        for(r=0; r<n; r++){
            sum += nums[r];
            
            //更新时，将长度缩到最短
            while(sum >= target && l <= r){
                ans = min(ans, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }
        
        if(ans == 0x3f3f3f3f) return 0;
        return ans;
    }
};

 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

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        bool check = false;
        string ans = s;
        int len = 0x3f3f3f3f;
        int n = s.length();
        int l = 0, r = 0;
        int cnt = 0;
        for(r=0; r<n; r++){
            if(s[r] == '1'){
                cnt++;
            }

            while(cnt == k){
                if(len >= r - l + 1) {
                    len = r - l + 1;
                    if(len == ans.length()){
                        ans = min(ans, s.substr(l, len));
                    }else{
                        ans = s.substr(l, len);
                    }
                    check = true; 
                }
                if(s[l] == '1') cnt--;
                l++;
            }
        }

        if(!check) return "";
        return ans;
    }
};

 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

class Solution {
public:
    int balancedString(string s) {
        int cnt['Z'];
        for(char c : s){
            cnt[c]++;
        }

        int n = s.size();
        int m = n / 4;
        if(cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m){
            return 0;
        }

        int ans = n;
        int l = 0;
        for(int r=0; r<n; r++){
            cnt[s[r]]--;
            
            while(cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m){
                ans = min(ans, r - l + 1);
                cnt[s[l]]++;
                l++;
            }
        }
        return ans;
    }
};

 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

class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        long long sum = 0;
        int n = nums.size();
        for(int i=0; i<n; i++){
            sum += nums[i];
        }

        int ans = (target / sum) * n;
        target %= sum;

        int l = 0;
        sum = 0;
        int ans2 = n;
        for(int r=0; r<2*n; r++){
            sum += nums[r % n];

            while(sum > target){
                sum -= nums[l % n];
                l++;
            }

            if(sum == target){
                ans2 = min(ans2, r - l + 1);
            }
        }

        if(ans2 == n) ans = -1;
        else ans += ans2;
        return ans;
    }
};

 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

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> ms, mt;
        int n = t.length();
        for(int i=0; i<n; i++){
            mt[t[i]]++;
        }

        n = s.length();
        int anslen = INT_MAX;
        int start = 0;
        int l = 0;
        int passed = 0;
        for(int r=0; r<n; r++){
            if(mt.contains(s[r])){
                ms[s[r]]++;
                if(ms[s[r]] == mt[s[r]]) passed++;
            }

            while(passed == mt.size()){
                int len = r - l + 1;
                if(len < anslen){
                    anslen = len;
                    start = l;
                }

                if(ms.count(s[l])){
                    ms[s[l]]--;
                    if(ms[s[l]] + 1 == mt[s[l]]){
                        passed--;
                    }
                }
                l++;
            }
        }
        string ans = anslen == INT_MAX ? "" : s.substr(start, anslen);
        return ans;
    }
};

/*
  刚开始的时候用一个check函数检查窗口是否符合条件：遍历整个mt，看是否每个字符都符合条件
  检查的时间复杂度：O(t.length())，超时。
  这没有发挥滑动窗口的作用，其实只需要检查将要pop和刚刚push进来的元素即可。O(1)
*/

 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

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<pair<int, int>> pairs;
        int numsn = nums.size();
        for(int i=0; i<numsn; i++){
            for(int x : nums[i]){
                pairs.emplace_back(x, i);
            }
        }
        sort(pairs.begin(), pairs.end());

        int l = 0;
        vector<int> cnt(numsn);
        int ok = 0;
        int ansl = 0, ansr = 0, anslen = 0x3f3f3f3f;
        int n = pairs.size();
        for(int r = 0; r < n; r++){
            if(cnt[pairs[r].second] == 0){
                ok++;
            }
            cnt[pairs[r].second]++;

            while(ok == numsn){
                //在循环里更新答案，因为出了循环就不符合条件了，届时很难判断
                if(pairs[r].first - pairs[l].first < anslen){
                    ansl = pairs[l].first;
                    ansr = pairs[r].first;
                    anslen = ansr - ansl;
                }

                cnt[pairs[l].second]--;
                if(cnt[pairs[l].second] == 0){
                    ok--;
                }
                l++;
            }
        }

        return {ansl, ansr};
    }
};