子数组和为k问题

关于各种子数组的和小于(大于)或等于k的最长最短子数组或者求有多少个这样的子数组问题,可以分成两类。

• 当数组全是正数的时候，用双指针算法
• 当数组存在负数的时候，用前缀和+哈希表优化，也可使用单调队列优化

求一个数组中和为k的子数组的个数

如果直接暴力做，复杂度为$O(n^2)$​​​​,不能通过。此题考虑前缀和+哈希表优化。我们定义$pre[i]$​​​为$[0,i]$​里所有的数的和，则$pre[i]$由$pre[i-1] + nums[i]$​​​​得来，即
$$
pre[i] = pre[i-1]+nums[i]
$$
那么找到一个子数组$[j…i]$和为$k$​这个条件可以转化成
$$
pre[j-1]==pre[i]-k
$$
于是问题就变为考虑以$i$结尾的和为$k$的连续子数组时，只要统计有多少个前缀和为$pre[i]-k$的$pre[j]$​​​​即可。

我们建立哈希表$mp$​，以和为键值，到当前位置出现次数为对应值，记录$pre[i]$出现的次数，从左往右边更新边计算答案，那么以$i$为结尾的答案$mp[pre[i]-k]$即可在$O(1)$时间内得到。最后答案即为所有$mp[pre[i]-k]$​​的和。

需要注意的是，因为我们从左往右边更新边计算时保证了$mp[pre[i]-k]$​​里记录的$pre[j]$​​的下标范围是$0 \leq j \leq i$​​.同时，由于$pre[i]$​​只与前一项$pre[j-1]$​有关，因此我们不必建前缀和数组，直接使用$pre$​​变量来记录和即可。

int subarraySum(vector<int>& nums,int k) {
    unordered_map<int,int> mp;
    int count = 0,pre = 0;
    mp[0] = 1;  //当前前缀和就为k时是存在一个子数组的
    for(auto x:nums){
        pre += x;
        if(mp.find(pre-k) != mp.end())
            count += mp[pre-k];
        mp[pre]++;
    }
    return count;
}

求一个数组中和为数组长度的子数组个数

这个题是在训练群中听学长的面试官同事提的。咋一看比较没有思路，但是把数组每个元素减1，就变成了子数组和为0，和上题一样。

求一个数组中和为k的最长子数组长度

仍然是前缀和+哈希表方式。这时哈希表以和为键，以右端点为对应值。当存在$mp[pre[i]-k]$​​时，也就是找到了一段和为$k$的子数组，这时比较$maxlen$和$i-mp[pre-k]$​​​更新答案即可。

int maxlenOfArray(vector<int>& nums,int k) {
    unordered_map<int,int> mp;
    mp[0] = -1;
    int maxlen = 0,pre = 0;
    for(int i = 0;i < nums.size();i++) {
        pre += nums[i];
        if(mp.find(pre-k))
            maxlen = maxlen>i-mp[pre-k]?maxlen:i-mp[pre-k];
        if(mp.find(pre) == mp.end()) 
        	mp[pre] = i//总是在第一次遇到这个和时插入map，使这个值尽可能早
    }
    return maxlen;
}

求一个01串中最长01数量相等的子串

此题将$0$​看做$-1$，则是找和为$0$​​的最长子串长度。

2021 CCPC Command Sequence

题意

一个机器人能上下左右移动，分别对应字符$UDLR$​.给定一个机器人移动序列字符串，问有多少个子串可以使其按照子串的顺序来走能回到原点。

分析

此题我们直接将每个字符看成一个数字，且上下互为相反数，左右互为相反数，那么就是找到这个数字序列有多少个和为$0$​​的子序列。依旧是前缀和+哈希表结构。需要注意的是，由于一个$2$​​可以由两个$-1$​​抵消，所以上下和左右代表的数字不能太接近。这里字符串长度最大为$10^5$​​，所以我们可以让$U$​和$D$​代表$1$​和$-1$​，让$L$​和$R$​代表$100000$​和$-100000$​​​​​​​​。

代码

#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int t, n;
ll a[maxn];
char s[maxn];

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s + 1;
        for (int i = 1; i <= n; i++)
        {
            if (s[i] == 'U')
                a[i] = 1;
            if (s[i] == 'D')
                a[i] = -1;
            if (s[i] == 'L')
                a[i] = 100000;
            if (s[i] == 'R')
                a[i] = -100000;
        }
        unordered_map<ll, int> mp;
        mp[0] = 1;
        ll pre = 0, count = 0;
        for (int i = 1; i <= n; i++)
        {
            pre += a[i];
            if (mp.find(pre) != mp.end())
                count += mp[pre];
            mp[pre]++;
        }
        cout << count << endl;
    }
    return 0;
}

数学？

题目描述

给你一个长度为$n$​的数组$a$​和一个正整数$k$​，问$a$​有多少个和$\geq k$​的​​连续子序列。

分析

如果连续子序列$[l,r]$的和已经$\geq k$,那么从$l$到$r+1$、从$l$到$r+2$​、$\cdots$、从$l$到$n$的和都$\geq k$。这样的子序列有$n-r+1$个。因此，我们可以枚举$l$从$1$到$n$，对于每一个$l$，找到最小的$r$使得$\sum[l,r]\geq k$,那么从$l$开始的符合条件的子序列就有$n-r+1$个。

对于给定的左边界$l$，如何快速找到最小满足条件的$r$,可以使用滑动窗口的办法。

我们得到上一个$l$的最小$r$之后，记录下这个最小的$r$和$[l,r]$的和。当$l$变成$l+1$时，让上次的和减去$a[l]$,得到的是$[l+1,r]$的和。

如果这个和仍大于等于$k$，那么$r$仍然是最小的$r$，更新答案即可。

否则$r$向右移动变成$r+1$，和也加上$a[r+1]$，直到和又大于等于$k$，此时的$r$又是最小的$r$。

上述过程中，一旦$r$​超过数组范围就结束了。

$r$从$1$移到了$n$，时间复杂度为$O(n)$。

代码

#include <iostream>
using namespace std;
typedef long long ll;

ll a[100010];
int main() {
    int n;
    ll k;
    cin >> n >> k; 
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    ll ans = 0; // 答案
    ll left = 0, right = 0; // l和r初始值都是0
    ll sum = a[0]; // sum代表[left, right]的和
    while (right < n) { 
        if (sum >= k) { // sum[l, r] >= k
            ans += n - right;  
            sum -= a[left++]; // 枚举下一个l（l++），相应地sum也要减去不在范围内的a[l]
        } else { // sum[l, r] < k，还没找到最小的r
            sum += a[++right]; // r右移并累加入总和
        }
    }
    cout << ans << endl;
    return 0;
}