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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> m;
        int n = s.length();
        int l = 0, r = 0;
        int ans = 0;
        for(int i=0; i<n; i++){
            m[s[i]]++;
            r++;

            if(m[s[i]] > 1){
                int index = -1;
                //在窗口内找重复出现的字符的位置
                for(int j=l; j<i; j++){
                    if(s[j] == s[i]){
                        index = j;
                        break;
                    }
                } 
                //若重复的字符在窗口内，则更新l
                if(index >= l) l = index + 1;
                //不管重复的字符在哪，都将其出现次数置为1
                m[s[i]] = 1;
            }

            ans = max(ans, r - l);
        }
        return ans;
    }
};

//题解1，用unordered_map
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), ans = 0, left = 0;
        unordered_map<char, int> cnt; // 维护从下标 left 到下标 right 的字符
        for (int right = 0; right < n; right++) {
            char c = s[right];
            cnt[c]++;
            while (cnt[c] > 1) { // 窗口内有重复字母
                cnt[s[left]]--; // 移除窗口左端点字母
                left++; // 缩小窗口
            }
            ans = max(ans, right - left + 1); // 更新窗口长度最大值
        }
        return ans;
    }
};

//题解2，用unordered_set
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), ans = 0, left = 0;
        unordered_set<char> window; // 维护从下标 left 到下标 right 的字符
        for (int right = 0; right < n; right++) {
            char c = s[right];
            // 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
            // 所以要在加入 c 之前，先移出窗口内的 c
            while (window.contains(c)) { // 窗口内有 c
                window.erase(s[left]);
                left++; // 缩小窗口
            }
            window.insert(c); // 加入 c
            ans = max(ans, right - left + 1); // 更新窗口长度最大值
        }
        return ans;
    }
};

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

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int n = s.length(), ans = 0, left = 0;
        unordered_map<char, int> cnt; 
        for (int right = 0; right < n; right++) {
            char c = s[right];
            cnt[c]++;
            while (cnt[c] > 2) { 
                cnt[s[left]]--; 
                left++; 
            }
            ans = max(ans, right - left + 1); 
        }
        return ans;
    }
};

 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 longestSubarray(vector<int>& nums) {
        int ans = 0;
        int l = 0;
        int cnt = 0;
        int n = nums.size();
        for(int r = 0; r < n; r++){
            if(nums[r] == 0) cnt++;

            if(cnt > 1){
                while(cnt > 1){
                    if(nums[l] == 0) cnt--;
                    l++;
                }
            }

            ans = max(ans, r - l); //(r - l + 1) - 1 = 区间长 - 1， 因为要删去0
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int l = 0, r = 0;
        int n = nums.size();
        for(r = 0; r < n; r++){
            if(nums[r] <= (long long)nums[l] * k) continue;
            l++;
        }
        return n - (r - l);
    }
};

 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 equalSubstring(string s, string t, int maxCost) {
        int n = s.length();
        vector<int> cost(n);
        for(int i=0; i<n; i++){
            cost[i] = abs(s[i] - t[i]);
        }

        int ans = 0;
        int l = 0;
        int sum = 0;
        for(int r = 0; r < n; r++){
            sum += cost[r];

            if(sum <= maxCost) ans = max(ans, r - l + 1);

            if(sum > maxCost) sum -= cost[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

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> m;
        int n = fruits.size();
        int l = 0, r = 0;
        int ans = 0;
        for(r = 0; r < n; r++){
            m[fruits[r]]++;

            while(m.size() > 2){
                m[fruits[l]]--;
                //注意[]包含的东西，一开始写成m[fruits[l] == 0]，很难发现
                if(m[fruits[l]] == 0) m.erase(fruits[l]);
                l++;
            }

            ans = max(ans, r - l + 1);
        }
        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

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> m;
        int l = 0, r = 0;
        int sum = 0;
        int n = nums.size();
        for(r = 0; r < n; r++){
            m[nums[r]]++;
            sum += nums[r];

            while(m.size() != r - l + 1){
                m[nums[l]]--;
                if(m[nums[l]] == 0) m.erase(nums[l]);
                sum -= nums[l++];
            }

            ans = max(ans, sum);
        }
        return ans;
    }
};

//题解
class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> st;
        int ans = 0, s = 0, left = 0;
        for (int x : nums) {
            while (st.contains(x)) {
                st.erase(nums[left]);
                s -= nums[left];
                left++;
            }
            st.insert(x);
            s += x;
            ans = max(ans, s);
        }
        return ans;
    }
};

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

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        int ans = 0;
        int n = nums.size();
        int l = 0, r = 0;
        for(r=0; r<n; r++){
            m[nums[r]]++;

            while(m[nums[r]] > k){
                m[nums[l]]--;
                if(m[nums[l]] == 0) m.erase(nums[l]);
                l++;
            }

            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

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

class Solution {
public:
    int maxConsecutiveChar(string& answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int l = 0, r = 0, sum = 0; r < n; r++) {
            sum += answerKey[r] != ch;
            while (sum > k) {
                sum -= answerKey[l++] != ch;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(maxConsecutiveChar(answerKey, k, 'T'),
                   maxConsecutiveChar(answerKey, k, 'F'));
    }
};

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

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ans = 0;
        int cnt = 0;
        int l = 0;
        int n = nums.size();
        for(int r=0; r<n; r++){
            if(nums[r] == 0){
                cnt++;
            }

            if(cnt > k){
                if(nums[l] == 0) cnt--;
                l++;
            }

            if(cnt <= k){
                ans = max(ans, r - l + 1);
            }
        }
        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

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        int n = nums.size();
        for(int i=0; i<n; i++){
            sum += nums[i];
        }
        int target = sum - x;
        
        int ans = 0;
        bool check = false;
        int l = 0;
        sum = 0;
        for(int r=0; r<n; r++){
            sum += nums[r];

            while(sum > target && l <= r){
                sum -= nums[l++];
            }

            if(sum == target){
                check = true;
                ans = max(ans, r - l + 1);
            }
        }
        if(check) ans = n - ans;
        else ans = -1;
        return ans;
    }
};