Leetcode-0x3f题单

Word count: 8.4k   |   Reading time≈ 37 min

计划

如何科学刷题？https://leetcode.cn/circle/discuss/RvFUtj/

目标：掌握基础算法，每一类型至少做10题左右，循序渐进。

a.定长滑动窗口

这类题往往是求某个固定长度内满足某种条件的最大值、最小值，一般处理思路是：

  • 向窗口中累加元素
  • 如果窗口长度已经到达固定长度，更新答案
  • 移出窗口最左边的元素，继续往后走

最少交换次数来组合所有的 1 II

怎么提炼出定长窗口？

因为我们可以交换任意两个不同位置的值，所以一定可以把所有的1聚合在一起，那么1的个数就是窗口的长度，滑动时，我们看窗口内缺多少个1，就需要交换多少次。

怎么处理环形？

在原数组后面再加上一次原数组，这样窗口往后滑动的时候，就可以连上前面的元素，模拟环形。

滑动子数组的美丽值

这道题有明显的暗示，求出每个长度为k的子数组…

怎么求第x小？

观察数组元素的数据范围，发现范围很小，那么我们就可以用一个数组去记录每个元素出现的次数即可，这样每次从最小的元素开始遍历，就可以找到第x小。

思考：如果数组元素范围很大怎么办？

子串的最大出现次数

这道题有一个迷惑的地方，就是不需要关注maxsize，因为既然minsize已经满足条件的话，为什么还需要再往后加呢，满足maxsize的话一定满足minsize，所以窗口的长度固定为minisize！

可获得的最大点数

几张卡牌 ****排成一行，每张卡牌都有一个对应的点数。点数由整数数组 <font style="color:rgba(38, 38, 38, 0.75);background-color:rgb(240, 240, 240);">cardPoints</font> 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 <font style="color:rgba(38, 38, 38, 0.75);background-color:rgb(240, 240, 240);">k</font> 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 <font style="color:rgba(38, 38, 38, 0.75);background-color:rgb(240, 240, 240);">cardPoints</font> 和整数 <font style="color:rgba(38, 38, 38, 0.75);background-color:rgb(240, 240, 240);">k</font>，请你返回可以获得的最大点数。

关键词： 排成一行，正好拿k张

1.按照题意模拟来做，前面拿m张，后面就是拿k-m张，使用前缀和和后缀和来计算答案

时间复杂度：O(n)

空间复杂度：O(n)

2.定长滑动窗口，窗口大小为n-k，剩下的数量就是k，滑一遍，一边滑一边更新答案即可。

时间复杂度: O(n)

空间复杂度： O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int ans{INT_MAX}, left{0}, len(n-k), tmp{0};
    int sum = accumulate(cardPoints.begin(), cardPoints.end(), 0);
    if(len == 0) return sum;
    for(int right = 0; right < n; ++right){
        tmp += cardPoints[right];
        if(right - left + 1 < len) continue;
        ans = min(ans, tmp);
        tmp -= cardPoints[left++];
    }
    return sum - ans;
}

b.不定长滑动窗口

和定长滑动窗口的区别是，我们不限制窗口大小，大概思路是，开始之后就一直找，直到不满足窗口的条件，然后剔除最左边的元素，继续向后扩展。

01月12日update: 上面说的开始之后就一直找，直到不满足窗口的条件。 这里不太准确，可能分成很多种情况:

  • 答案可能是我们维护的窗口大小，所以我们要时刻保证窗口是满足条件，所以一旦窗口不满足条件后，我们要一直移除left的元素，然后循环外更新答案（如，最大连续1的个数，最高频元素的频数，）
  • 答案是把我们的窗口排除掉所剩下的元素所构成的集合，我们是时刻保证窗口外是满足条件的，这其实与1是相同的，很多时候考虑题目使用逆向思维（如，每种字符至少取k个，替换子串获得平衡字符串
  • ）

最大连续1的个数 III

最大可以翻转k个0变成1，也就是说我们可以容忍窗口中最多含有k个0，所以在扩展窗口时考虑这一点即可，剔除左边元素时，如果是0，那么一定用了翻转次数，记得复原。

1
2
3
4
5
6
7
8
9
10
11
int left{0};
int zero{0};
for(int right  = 0; right < n; ++right){
    if(nums[right] == 0) ++zero;  //加入窗口
    while(zero > k){              //不满足条件，一直增加left
        if(nums[left++] == 0){
            --zero;
        }
    }
    ans = max(ans, right - left + 1); //更新答案
}

最高频元素的频数

和最大连续1的个数类似，那一题是将0变成1，固定消耗是1，但是这一题是将最大消耗是k，让某个数出现的频率最高， 我们定义的窗口是所有的数字都是最后一个数(不够的数字用k来补充)，找到最大的窗口就是答案。

  • 代码中用last标记最后一个满足条件的窗口的最后一个元素，因为退出循环时right下标不一定符合条件
  • sum的维护需要注意，如果不满足记得减去nums[right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while(right < n){
               sum += nums[right];
               long long count = 1LL * (right - left + 1) * nums[right] - sum;
               if(count >= 0){
                   if(k >= count){
                       k -= count;
                       sum += count;
                       last = nums[right];
                       ans = max(ans, right - left + 1);
                   }else{
                       sum -= nums[right];    //不满足的right记得去掉
                       break;
                   }
               }
               right ++;
           }
           if(right == n) break;
           sum -= last;               //去掉包含的left，注意他已经变成last了
           k += last - nums[left++];  //收回消耗的k

下面有一种更简洁的写法：

1
2
3
4
5
6
7
8
9
10
long long sum{0};
sort(begin(nums), end(nums));
for(int right = 0; right < n; ++right){
    sum += nums[right];
    while(k < (1LL * (right - left + 1) * nums[right] - sum)){
        sum -= nums[left++];
    }
    ans = max(ans, right - left + 1);
}
return ans;

每种字符至少取 K 个

解法一:分类讨论

答案存在三种可能：

  • 只拿左边的
  • 只拿右边的
  • 两边都取

前两种是一样的，只用把字符串翻转一下就可以了。

第三种情况可以使用受限制的滑动窗口，为什么说是受限制的呢，因为我们不能一味地向后滑动，这样会将某个元素使用两次，所以right的移动要考虑left。

1
2
3
4
5
6
7
8
9
10
11
int left = 1, right = n + 1;
while(true){
    if(left > n -1) break;
    while(right <= n + left && (cnt[0] < k || cnt[1] < k || cnt[2] < k)){
        cnt[ss[right++]-'a'] ++;
    }
    if(cnt[0]>=k && cnt[1] >= k && cnt[2] >= k){
        ans = min(ans, right - left);
    }
    cnt[ss[left++]-'a']--;
}

解法二:逆向思维

我们只考虑滑动窗口，窗口内的元素是我们不取的，剩下的元素是取走的，那么我们保证这个窗口最大，且剩下的元素能够满足条件即可！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int takeCharacters(string s, int k) {
        int n = s.size();
        int cnt[3]{0, 0, 0};
        for(char c : s){
            cnt[c -'a'] ++;
        }
        if(cnt[0] < k || cnt[1] < k || cnt[2] < k) return -1;
        int ans{0}, left{0};
        for(int right = 0; right < n; ++right){
            cnt[s[right]-'a'] --;  //拿走当前的元素
            while(cnt[s[right]-'a'] < k){ //因为上面只拿走了当前的元素，仅可能当前这个元素不满足条件，我们尝试从还回去前面的left
                cnt[s[left++]-'a'] ++;
            }
            ans = max(ans, right - left + 1);   //找到最大的窗口
        }
        return n-ans;  //剩下的就是我们必须要取走的元素
    }
};

毯子覆盖的最多白色砖块数

收集连续 K 个袋子可以获得的最多硬币数量的简易版本，相当于权重全为1。

这题我们如何转移到滑动窗口上来呢，因为毯子的长度固定，所以无非是选取毯子的左端点或者右端点，一旦某一个端点固定，另一个也随之确定，所以我们考虑固定某一个端点。这道题考虑左端点和右端点是等价的，这里以右端点举例：

右端点只有可能在两个位置：1.区间上 2.空白处

对于第二种情况：可以看下图，有两种情况，我们将右端点向左移动，只会变得更好或者答案不变

对于第一种情况：可以看到，向右移动右端点不会让答案变得更差，①答案更好，②答案不变

所以针对以上讨论，我们可以将右端点固定在某个区间的右端点上，这样得到的答案肯定是最优的。

如何运用滑动窗口处理呢？

按左端点对所有区间排序，我们挨个添加当前的区间，因为右端点固定，我们可以计算出左端点，那么之前包括的区间还满足条件么，我们去掉不满足条件的点即可，一个特殊情况是左端点落在某个区间内部，我们只要减掉这个区间内我们没有覆盖到的点即可。

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
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        int ans{0};
        ranges::sort(tiles, {}, [](const auto& it) { return it[0];});  //cpp20:https://en.cppreference.com/w/cpp/algorithm/ranges/sort

        int left{0}, cover{0};
        int n = tiles.size();
        for(int right = 0; right < n; ++right){
            int l = tiles[right][0], r = tiles[right][1];
            //更新区间
            cover += (r-l+1);   
            //更新左端点
            while(r - carpetLen + 1 > tiles[left][1]){
                cover -= (tiles[left][1] - tiles[left][0] + 1);
                left ++;
            }
            //更新答案
            int uncover = max(0, tiles[right][1] - carpetLen + 1 - tiles[left][0]);
            ans = max(ans, cover - uncover);
            //std::cout << left <<" " << right << " " << cover <<" " << uncover << " " << l << " " << r << std::endl;
        }
        return ans;
    }
};

收集连续 K 个袋子可以获得的最多硬币数量

这道题相比毯子那题，就是给每个点位加了一个权重，我们还能只固定右端点计算么？答案是不对的，看下面这种case：

这种情况明显是固定左端点最优，所以这一题我们可以比较下使用左端点和使用右端点分别得到的答案，取一个最大值即可。

如何在使用左端点的情况下也可以复用之前的函数？

将每个区间按照原点做一个对称数组， 例如[1,5] 变成[-5, -1], 这样按照[1,5]的左端点就变成了按照[-5,-1]的右端点了，完成代码复用！

1
2
3
4
5
6
7
8
9
10
11
long long maximumCoins(vector<vector<int>>& coins, int k) {
    long long ans = maximumWhiteTiles(coins, k);

    for(auto& item : coins){
        int temp = item[0];
        item[0] = - item[1];
        item[1] = -temp;
    }
    ans = max(ans, maximumWhiteTiles(coins, k));
    return ans;
}

找出最长等值子数组

看了两个提示之后才有了正确的思路，哎，任重道远啊！

关键技巧：分组滑动窗口

等值子数组的关键性质就是，子数组中的所有元素都相等，那我们将所有的元素按值分组，分完组后，就可以只关注下标了，两个下标如过间隔相差大于1，那么之间的元素一定是需要删除的，这就有了消耗，我们一直向后滑，如过需要删除的元素大于k，我们就需要舍弃前面的元素，让滑动窗口内的消耗一直小于等于k。

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
int ans = 1;
for(const auto&[_, v] : h){
    int m = v.size();
    if(m <= ans) continue;
    int left{0}, len{1}, last{v[0]}, need_del{0};
    for(int right = 1; right < m; ++right){
        len++;
        if(v[right] - last > 1){
            need_del += v[right] - last - 1;
        }
        while(need_del > k){
            int second = left + 1;
            if(second == right){
                left = right;
                len = 1;
                need_del -= (v[right] - last - 1);
            }else{
                need_del -= (v[second] - v[left] - 1);
                len--;
                left ++;
            }
        }
        last = v[right];
        ans = max(ans, len);
    }
}

在做了这些题之后，可以发现不定长滑动窗口题的一些共通点：

  • 往往是一个数组
  • 往往是让我们找满足某个条件的最大/最小子数组/子串，就算不是，可能也需要间接转成这些问题
  • 还需要多做一些题。。。。

删除最短的子数组使剩余数组有序

TODO

暂时没有思路

替换子串得到平衡字符串

根据题意，容易看出我们的窗口就是待替换子串，因为我们可以将它替换成长度相同的任意字符串，所以我们只要保证窗口外的QWER的个数全部不大于n/4(如果有某个字符的数量超过n/4， 1是不符合题意，2是他多出来的部分无法替换，没有贡献)

  • right进入窗口
  • 当前是否满足条件，如果满足条件，尝试左移left，更新答案

只有两步的原因是，我们的循环内部是满足条件的，所以可以更新答案，舍去第三步

1
2
3
4
5
6
7
8
int left{0};
for(int right = 0; right < n; ++right){
    cnt[s[right]] --;
    while(cnt['Q'] <= n/4 && cnt['W'] <= n/4 && cnt['E'] <= n/4 && cnt['R'] <= n/4){
        ans = min(ans, right - left + 1);
        cnt[s[left++]] ++;
    }
}

1358. 包含所有三种字符的子字符串数目

这一题是一个新的类型，求子数组数量，这类问题一般考虑 ans += left.

以此题为例，要求我们求出abc三个字符都至少出现一次的子字符串，我们考虑一个满足条件最小的答案-每个字符只出现过一次！所以我们的窗口就是abc都至少出现过一次，如果right进来之后不满足条件，我们就尝试左移left，一旦跳出循环，我们让答案增加left个（为什么是left个，因为left++之后跳出while，当前left-right是不满足条件的，left-1到right才是满足条件的子串，但是考虑个数的话，要加上下标为0的那个子串）一句话总结，如果left不为0，那么一定是满足了子串的条件导致left左移！！！

1
2
3
4
5
6
7
8
9
int ans{0}, left{0};
int cnt[3]{0};
for(int right = 0; right < n; ++right){
    cnt[s[right]-'a']++;                              //right进来
    while(cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1){ //如果满足条件了
        cnt[s[left++]-'a']--;                         //左移left
    } 
    ans += left;                                      //当前left不为0的话，一定是满足了while的条件导致移动了
}

2962. 统计最大元素出现至少 K 次的子数组

与上面一题类似，条件是窗口内的最大元素至少出现k次，代码类似
好好理解为什么ans+=left是对的

其实这个答案更新的过程我觉得可以将left理解成移动的次数，for example， nums = [3, 3], k = 1, ans=3:
1.right = 0, cnt = 1, 满足条件， left = 1， exit loop， ans += 1

2.right = 1, cnt = 1, 满足条件， left = 2， exit loop， ans += 2

进入循环，left加1，表示0-left的所以下标都可以与right组合成答案，left移动的次数就是当前子串的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long ans{0};
int mx = *max_element(begin(nums), end(nums));
int left{0}, cnt{0};
int n = nums.size();
for(int right = 0; right < n; ++right){
    if(mx == nums[right]) cnt ++;
    while(cnt >=k){
        if(nums[left++] == mx){
            --cnt;
        }
    }
    ans += left;
}
return ans;

3325. 字符至少出现 K 次的子字符串 I

求子数组个数问题，因为只有小写字母，所以我们可以用数组来记录每个元素出现的次数，窗口内的条件就是某个字符出现的次数大于等于k个，答案的更新和上面一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cnt[26]{0}, left{0};
auto check = [&cnt, k]()->bool{
   for(int i = 0; i<26; ++i){
       if(cnt[i] >= k) return true;
   }
   return false;
};
for(int right = 0; right < n; ++right){
   cnt[s[right]-'a']++;
   while(check()){
       cnt[s[left++]-'a']--;
   }
   ans += left;
}

2799. 统计完全子数组的数目

求子数组个数问题，先求不同元素数目，然后窗口内的条件就是元素出现的次数要大于等于整个数组不同元素数目，答案更新和上面一致。

1
2
3
4
5
6
7
8
9
10
11
12
map<int, int> h;
for(int right = 0; right < n; ++right){
    h[nums[right]] ++;
    while(h.size() >= k){
        if(--h[nums[left]] == 0){
            h.erase(nums[left]);
        }
        left++;
    }
    ans += left;
}
return ans;

2537. 统计好子数组的数目

求子数组个数问题，这道题窗口的条件判断类似上面的题，唯一需要注意的是更新维护的值，在注释中解释：

注释掉的代码是我的第一版，比较繁琐，其实主要考虑是当前这个元素的影响在最后再加到窗口中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int left{0}, cnt{0};
        unordered_map<int, int> h;
        for(int right = 0; right < n; ++right){
            cnt += h[nums[right]]++;
            while(cnt >= k){
                // if(nums[left] == nums[right]){
                //     cnt -= h[nums[left]];
                // }else{
                //     if(h[nums[left]] > 1) cnt -= h[nums[left]] - 1;
                // }
                // h[nums[left++]]--;
                cnt -= --h[nums[left++]];  //111...1, 删掉第一个1的影响是少了4-1个下标对
                //left++;
            }
            ans += left;
            //h[nums[right]]++;
        }
        return ans;

713. 乘积小于 K 的子数组

此题属于求子数组个数问题中的越短越合法，考虑当前新增元素right，如果窗口[left, right]复合条件的话，那么会新增多少个答案？[left…right], [left+1, ….right], ….., [right] 一共right - left + 1个。

注意题目数据范围，k不大于1的时候答案一定是0

1
2
3
4
5
6
7
8
9
10
11
if(k <= 1) return 0;
int n = nums.size();
int t{1}, left{0}, ans{0};
for(int right = 0; right < n; ++right){
    t *= nums[right];
    while(t >= k){
        t /= nums[left++];
    }
    ans += (right - left + 1);
}
return ans;

2302. 统计得分小于 K 的子数组数目

和上道题一样，只不过窗口的条件计算不一样

01月14日Thinking: 滑动窗口一定基于一个连续的性质？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long ans{0}, score{0}, sum{0};
int n = nums.size();
if(k == 1) return 0;
int left{0};
for(int right = 0; right < n; ++right){
    sum += nums[right];
    score = sum * (right - left + 1);
    while(score >= k){
        sum -= nums[left++];
        score = sum * (right - left + 1);
    }
    ans += (right - left + 1);
}
return ans;

2762. 不间断子数组

求子数组问题，这题的关键在于怎么判断当前新加的元素是否满足条件，容易看出，只要之前的窗口中最小值和最大值与当前元素的差的绝对值小于等于2，就满足条件，那么是不是只需要维护最小值和最大值就可以了呢？显然不是，一旦最小值滑出去了，怎么快速地知道新的最小值呢，所以我们这里可以借用map，它的所有键都是排序的，这样就能快速找到最小值最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left{0};
map<int, int> mp;
for(int right = 0; right < n; ++right){
    mp[nums[right]]++;
    while(!mp.empty() && (abs(mp.begin()->first-nums[right]) > 2
    || abs(mp.rbegin()->first-nums[right]) > 2)){
        int t = nums[left];
        if(--mp[t] == 0){
            mp.erase(t);
        }
        ++left;
    }
    ans += right - left + 1;
}
return ans;

930. 和相同的二元子数组 = 560. 和为 K 的子数组 （560不能使用滑动窗口！！）

恰好型滑动窗口解法：

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 ≥𝑘 的子数组。
计算有多少个元素和 ＞𝑘 的子数组，也就是 ≥𝑘+1 的子数组。答案就是元素和 ≥𝑘 的子数组个数，减去元素和 ≥𝑘+1的子数组个数。这里把 ＞转换成 ≥，从而可以把滑窗逻辑封装成一个函数 f，然后用 f(k) - f(k + 1) 计算，无需编写两份滑窗代码。

总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。

注：也可以把问题变成 ≤𝑘 减去 ≤ 𝑘−1（两个至多）。可根据题目选择合适的变形方式。

具体到这一题，是非常贴切上面的描述的，cnt1是大于等于goal的个数，cnt2是大于等于goal+1的个数即大于k的个数（因为数组元素都是整数），cnt2是cnt1的真子集，其补集就是等于goal的个数！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ans{0}, sum1{0}, sum2{0}, left1{0}, left2{0};
int cnt1{0}, cnt2{0};
for(int right = 0; right < nums.size(); ++right){
    sum1 += nums[right];
    sum2 += nums[right];

    //>=
    while(left1 <= right && sum1 >= goal){
        sum1 -= nums[left1++];
        cnt1 ++;
    }
    while(left2 <= right && sum2 >= goal + 1){
        sum2 -= nums[left2++];
        cnt2++;
    }
    ans += (cnt1 - cnt2);
    //cout << right <<" " << cnt1 <<" " << cnt2 << endl;
}
return ans;

为什么560不能使用滑动窗口？

因为这一题的子数组和不能保证非递减的，那我们移除left的元素造成的影响就是不确定的？具体一点的例子就是[-1, -1, 1, 1], k = 0, 数组加完都不满足条件， 如果是[0, 0, 1] 甚至是[-1, 0, 1], 我们不断地排除left一定会让窗口的也会慢慢变小(思考一下这里！！）

c.常用数据结构

(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)

0.技巧-枚举右，维护左

对于双变量问题，例如求两数之和a+b=c，我们可以枚举b，转换成单变量问题，也就是在b左边查找是否含有c-b，而这可以用哈希表维护，这个技巧称之为枚举右，维护左。

来几个例题感受下思想：

1814. 统计一个数组中好对子的数目

要求

  • <font style="color:rgba(38, 38, 38, 0.75);background-color:rgb(240, 240, 240);">nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])</font>

交换一下，即nums[i] -rev(nums[i] == nums[j] - rev(nums[j])

那我们只需要枚举元素nums[i]，在枚举的同时在哈希中记录下nums[i]-rev(nums[i])

记录之前，先看看哈希中有没有这个值，有几个就代表之前出现了几次与当前元素凑成对子的数字，累加到答案中即可。这就是枚举右，维护左！

1
2
3
4
5
6
7
8
9
10
11
unordered_map<int, int> h;
int ans{0};
constexpr int mod = 1e9+7;
for(int i = 0; i<nums.size(); ++i){
    string tmp = to_string(nums[i]);  //枚举右
    reverse(tmp.begin(), tmp.end());
    int rev = stoi(tmp);
    ans = (ans + h[nums[i] - rev])%mod;
    h[nums[i] -rev]++;   //维护左
}
return ans;

1031. 两个非重叠子数组的最大和

这题和上面那一题不对，要求求两个非重叠子数组元素的最大和。

首先，我们可以求前缀和，那么每个元素为开始/结尾且长度为firstLen或者secondLen的子数组和我们都能O(1)的求出来。既然如此，我们尝试枚举某个元素，我可以当即知道这个元素为start且长度为firstLen或secondLen的子数组之和，我肯定想知道前面的元素中最大的长度为firstLen/secondLen的子数组和，这就是维护左，我们可以用一个变量记录下出现过的长度为firstLen或者secondLen的子数组和，尝试更新答案即可。

我的代码中是这样 0…..i-1 , i … 记录每个元素为结尾的长度为firstLen和secondLen的子数组和，然后在遍历的过程中维护左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> pre(n+1, 0);
vector<int> p_fi(n+1, 0);
vector<int> p_se(n+1, 0);
for(int i = 1; i<=n; ++i) { 
    pre[i] = pre[i-1] + nums[i-1];
    if(i >= firstLen) p_fi[i] = pre[i] - pre[i-firstLen];
    if(i >= secondLen) p_se[i] = pre[i] - pre[i-secondLen];
}

int ans{0}, mx_f{0}, mx_s{0};
for(int i = min(firstLen, secondLen); i<=n; ++i){
    if(i > firstLen){
        if(i+secondLen-1 <= n) ans = max(ans, mx_f + pre[i+secondLen-1] - pre[i-1]);
    }
    if(i > secondLen){
        if(i+firstLen-1 <= n) ans = max(ans, mx_s + pre[i+firstLen-1] - pre[i-1]);
    }
    if(i >= firstLen) mx_f = max(mx_f, p_fi[i]);
    if(i >= secondLen) mx_s = max(mx_s, p_se[i]);
}
return ans;

1930. 长度为 3 的不同回文子序列

本题不同于上面两题，是三个变量，枚举中间变量比较好处理。

前后可以分别用前缀和及后缀和来维护，来看第一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n = s.size();
vector<vector<int>> p(n+1, vector<int>(26, 0));
for(int i = 1; i<=n; ++i){
    for(int j = 0; j<26; ++j){
        if(j == s[i-1]-'a') p[i][j] = p[i-1][j] + 1;
        else p[i][j] = p[i-1][j];
    }
    
}
map<pair<int,int>, bool> h;
int ans{0};
for(int i = 2; i<=n-1; ++i){
    for(int j = 0; j<26; ++j){
        if(p[i-1][j] && (p[n][j]-p[i][j]) && !h[{s[i-1]-'a', j}]){
            h[{s[i-1]-'a', j}] = true;
            ans++;
        } 
        
    }
}
return ans;

看看如何优化：

首先空间上，是不是一定需要二维数组？

不是，前缀和我们可以维护左的思想来做，那么后缀和呢，是不是先算一遍前缀和，然后把当前已经遍历过的元素减掉就可以了，所以一维数组就可以，如此，时间上也少了一层循环！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n = s.size();
vector<int> pre(26, 0), suf(26, 0);
for(int i = 1; i<n; ++i){
    ++suf[s[i]-'a'];
}

map<pair<int,int>, bool> h;
int ans{0};
for(int i = 1; i<n-1; ++i){
    ++pre[s[i-1]-'a'];
    --suf[s[i]-'a'];

    for(int j = 0; j<26; ++j){
        if(pre[j] && suf[j] && !h[{s[i]-'a', j}]){
            h[{s[i]-'a', j}] = true;
            ans++;
        } 
        
    }
}
return ans;

进一步优化，这个map可以优化成一个常数上的查询，我们使用一个26*26的二维数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n = s.size();
vector<int> pre(26, 0), suf(26, 0);
for(int i = 1; i<n; ++i){
    ++suf[s[i]-'a'];
}

bool h[26][26]{0};
int ans{0};
for(int i = 1; i<n-1; ++i){
    ++pre[s[i-1]-'a'];
    --suf[s[i]-'a'];

    for(int j = 0; j<26; ++j){
        if(pre[j] && suf[j] && !h[s[i]-'a'][j]){
            h[s[i]-'a'][j] = true;
            ans++;
        } 
        
    }
}
return ans;

2874. 有序三元组中的最大值 II

本题是三元组(i, j, k), 要求(nums[i] - nums[j] ) * nums[k]的最大值

  • 1.我们可以枚举j，这要维护前缀最大值和后缀最大值即可， 时间复杂度和空间复杂度都是O(n)
  • 2.我们可以枚举k，那么只要维护nums[i]-nums[j]的最大值即可， 参考121. 买卖股票的最佳时机，维护前面的最大值mx和前面的最大利润，然后枚举k计算更新ans
1
2
3
4
5
6
7
8
9
long long ans{0};
int n = nums.size();
int mx {0}, i_minus_j{0};
for(int i = 0; i<n; ++i){
    ans = max(ans,  i_minus_j * 1LL * nums[i]);
    i_minus_j = max(i_minus_j, mx - nums[i]);
    mx = max(mx, nums[i]);
}
return ans;

1.前缀和

s[i] = s[i-1] + cur[i];

s[0] = 0;

如此，计算子数组和我们就可以O(1)的方式计算出，相当于空间换时间。

2055. 蜡烛之间的盘子

题意太长，跳转link查看原题。

给出了一个区间的左右端点，我们可以利用只记录盘子的前缀和来计算出数量，但是问题就是左右端点可能不一定满足条件，容易看出，只要找出区间内最靠近左端点和右端点的蜡烛，我们就能得到正确的答案！

  • 方法一：利用二分，我们可以将蜡烛的下表放在一个数组里，然后对于query的左右端点，分别找到最近的蜡烛，就可以找到答案

空间复杂度：O(N)

时间复杂度：O(NlogN)

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:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> pre(n+1, 0), idx;
        for(int i = 0; i<n; ++i){
            pre[i+1] = pre[i] + (s[i] == '*' ? 1:0);
            if(s[i] == '|'){
                idx.emplace_back(i);
            }
        }

        vector<int> ans(queries.size(), 0);
        int no{0}, m = idx.size();
        for(const auto& q : queries){
            int l = q[0], r = q[1];
            auto lit = lower_bound(begin(idx), end(idx), l) - begin(idx);
            auto rit = upper_bound(begin(idx), end(idx), r) - begin(idx) - 1;
            //cout << idx[lit] <<" " << idx[rit] <<endl;
            if((lit >=0 && lit < m && rit >=0 && rit < m) && idx[lit] >= l && idx[lit] <= r && idx[rit] >= l && idx[rit] <= r){
                ans[no++] = pre[idx[rit]+1] - pre[idx[lit]];
            }else{
                ans[no++] = 0;
            }
        }
        return ans;
    }
};
  • 我们维护每个盘子最近的蜡烛就可以了，左边最近的和右边最近的(左端点左边的蜡烛如果不满足条件，就使用右边的蜡烛！

空间复杂度: O(N)

时间复杂度：O(N)

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
class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> pre(n+1, 0), left(n, -1);
        int l{-1};
        for(int i = 0; i<n; ++i){
            pre[i+1] = pre[i] + (s[i] == '*' ? 1:0);
            if(s[i] == '|'){
                l = i;
            }
            left[i] = l;
        }

        vector<int> right(n, -1);
        int r{-1};
        for(int i = n-1; i>=0; --i){
            if(s[i] == '|'){
                r = i;
            }
            right[i] = r;
        }

        vector<int> ans(queries.size(), 0);
        int no{0};
        for(const auto& q : queries){
            l = q[0], r = q[1];
            int left_p = left[l];
            if(left_p < l) left_p = right[l];
            int right_p = left[r];
            if(left_p <= right_p && left_p != -1){
                ans[no++] = pre[right_p+1] - pre[left_p];
            }else{
                ans[no++] = 0;
            }
        }
        return ans;
    }
};

提交后发现，对于vector，我们使用[]运算符和at所有的时间是不一样的，应该是at多了下标检查这一步所以花费了一些时间。

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
     reference
     operator[](size_type __n) _GLIBCXX_NOEXCEPT
     { return *(this->_M_impl._M_start + __n); }

     const_reference
     operator[](size_type __n) const _GLIBCXX_NOEXCEPT
     { return *(this->_M_impl._M_start + __n); }

   protected:
     /// Safety check used only from at().
     void
     _M_range_check(size_type __n) const
     {
if (__n >= this->size())
  __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
			       "(which is %zu) >= this->size() "
			       "(which is %zu)"),
			   __n, this->size());
     }

   public:
     /**
      *  @brief  Provides access to the data contained in the %vector.
      *  @param __n The index of the element for which data should be
      *  accessed.
      *  @return  Read/write reference to data.
      *  @throw  std::out_of_range  If @a __n is an invalid index.
      *
      *  This function provides for safer data access.  The parameter
      *  is first checked that it is in the range of the vector.  The
      *  function throws out_of_range if the check fails.
      */
     reference
     at(size_type __n)
     {
_M_range_check(__n);
return (*this)[__n]; 
     }

930. 和相同的二元子数组 = 560. 和为 K 的子数组

这两道题几乎完全一样，因为所有的子数组和都可以通过前缀和求出来。所以我们可以利用哈希表记录所有的前缀和，然后遍历，遍历的时候发现所以当前前缀和sum减去我们的goal有在哈希表中出现的话，就有了构成和为k的子数组，我们累加到答案中即可。

时间复杂度：O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
int subarraySum(vector<int>& nums, int k) {
    int ans{0}, pre{0};
    unordered_map<int, int> h;
    h[0] = 1;
    for(int x : nums){
        pre += x;
        ans += h[pre - k];
        h[pre]++;
    }
    return ans;
}

这道题其实可以通过滑动窗口来求解，恰好型滑动窗口，更新在不定长滑动窗口一节中

1524. 和为奇数的子数组数目

子数组的和可以由两个前缀和相减得到，我们维护两个变量，一个记录奇数前缀和的个数，一个记录偶数前缀和的个数，分情况更新答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int n = arr.size();
        int odd{0}, even{1};
        constexpr const int mod = 1e9+7;
        int sum {0}, ans{0};
        for(int i = 0; i<n; ++i){
            sum += arr[i];
            if(sum & 1){
                ans = (ans + even) % mod;
                ++ odd;
            }else{
                ans = (ans + odd) % mod;
                ++ even;
            }
        }
        return ans;
    }
};

3026. 最大好子数组和

给你一个长度为 n 的数组 nums 和一个 正 整数 k 。
如果 nums 的一个子数组中，第一个元素和最后一个元素 差的绝对值恰好 为 k ，我们称这个子数组为 好 的。换句话说，如果子数组 nums[i..j] 满足 |nums[i] - nums[j]| == k ，那么它是一个好子数组。
请你返回 nums 中 好 子数组的 最大 和，如果没有好子数组，返回 0

i…j…k

假如（i, k）和（j, k）都满足条件，我们取max( sum(i…k), sum(j…k))

而子数组和可以通过前缀和求出，所以我们维护i和j的前缀和，容易看出来，维护最小的有意义，因为prek确定，sumi或者sumj越小，答案越大，我们用一个map存储下每个val对应的最小的前缀和即可

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:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long ans{LLONG_MIN}, sum{0};
        std::unordered_map<int, long long> h;
        for(int i : nums) {
            sum += i;
            if(h.count(i + k)){
                ans = max(ans, sum - h[i + k]);
            }
            if(h.count(i - k)){
                ans = max(ans, sum - h[i - k]);
            }

            if(!h.count(i)){
                h[i] = sum - i;
            }else{
                h[i] = min(h[i], sum - i);
            }
        }
        return ans == LLONG_MIN ? 0 : ans;
    }
};
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2015-2025 Xudong0722
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信