前缀和与子数组

发表于 更新于

相似题目

ref : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solution/xi-fa-dai-ni-xue-suan-fa-yi-ci-gao-ding-qian-zhui-/

模板

例题1 (presum)

有 N 个的正整数放到数组 A 里，现在要求一个新的数组 B，新数组的第 i 个数 B[i]是原数组 A 第 0 到第 i 个数的和。

求解：正常前缀和

1
2
3
4
5
6
vector<int> sum;
int n = sum.size();
vector<int> psum(n+1);
vector<int> psum1(n);
psum[i] = psum[i-1]+sum[i];   // [l,r] ->  psum[r] - psum[l-1]
psum1[i] = psum[i-1]+sum[i-1]; // [l, r] -> psum[r+1] - psum[l];

例题2 (countArray)

求一个数组的连续子数组总个数。比如 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，需要返回 6。

总的连续子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + … + 以索引为 n - 1 结尾的子数组个数。

利用 例题1 的前缀和思路， 边遍历边求和。

1
2
3
4
5
6
7
8
int countArray(vector<int> nums){
	int ans = 0;
    int temp = 1;
    for(auto& a: nums){
        temp+=1;
        ans+=k;
    }
}
  • 时间复杂度：O(N)，其中 N 为数组长度。
  • 空间复杂度：O(1)

例题3 (countArrayGapK)

求一个数组相邻差为 1 连续子数组的总个数，就是索引差 1 的同时，值也差 1。

1
2
3
4
5
6
7
8
9
10
11
12
int countArrayGap1(vector<int> nums){
	int n = nums.size();
    int ans = 0;
    int temp = 1;
    for(int i = 1;i<n;++i){
        if(nums[i] = nums[i-1] + 1){
            temp+=1;
        }else{
            temp = 0;
        }
    }
}

例题4 (countArrayLessEqualK)

求出不大于 k 的子数组的个数。不大于 k 指的是子数组的全部元素都不大于 k。 比如 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，不大于 3 的子数组有 [1], [3], [1,3] ，那么 [1,3,4] 不大于 3 的子数组个数就是 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countArrayLessK(int k, vector<int> nums){
	int n = nums.size();
    int ans = 0;
    int temp = 0;
    for(int i = 0;i<n;++i){
        if(nums[i] <= k){
            temp++;
        }else{
            temp = 0;
        }
        ans+=temp;
    }
    return ans;
}

例题5(countArraMostEqualK)

求出子数组最大值刚好是 k 的子数组的个数。 比如 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，子数组最大值刚好是 3 的子数组有 [3], [1,3] ，那么 [1,3,4] 子数组最大值刚好是 3 的子数组个数就是 2。

1
2
3
int countArraMostEqualK(int k1, int k2, vector<int> nums){
    
}

子数组最大值刚好是k的子数组的个数 countArraMostEqualK可以使用求不大于k的子数组的方法countArrayLessEqualK 来求解，即

countArraMostEqualK(k) = countArrayLessK (k) - countArrayLessK (k-1)

例题6 (countArraBetween)

求出子数组最大值刚好是 介于 k1 和 k2 的子数组的个数。

countArraBetween(k1, k2, nums) 等价于

countArrayLessK(k2, nums) - countArrayLessK(k1 - 1, nums), k2>k1

1
2
3
int countArraBetween(int k1, int k2, vector<int> nums){
    
}

小于等于 k2 的区域 减去 小于 k1 的区域 就是 大于等于 k1 且小于等于 k2 的区域。

467. 环绕字符串中唯一的子字符串

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….” .
现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。 

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

输入: p = "a"
输出: 1
解释: 字符串 s 中只有一个"a"子字符。
示例 2:

输入: p = "cac"
输出: 2
解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:

输入: p = "zab"
输出: 6
解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。


提示:
1 <= p.length <= 10^5
p 由小写英文字母构成

套模板3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void case467(string p){
	int ans = 0;
    int n = p.size();
    int temp = 1;
    for(int i = 1;i<n;++i){
        if((p[i] == 'a' && p[i-1] =='z') || (p[i]-'a') == (p[i-1] - 'a' + 26 + 1)%26){
            // 连续
            temp++;
        }else{ // 不连续
            temp = 1;
        }
        ans+=temp;
    }
    return ans;
}

直接套模板是错误的，因为对于cac这种情况，返回值是3， 但实际上是2，因为c被计算了两次，这就意味着需要去重，如果对于输入abcd使用set去重可以看到

1
2
3
4
5
6
7
8
a
b
c
ab (a, b)
cd  (c, d)
abc (a,b,c,ab,bc,abc)
bcd (b,c,d,bc,cd,bcd)
abcd (....)

发现set中的元素是连续的，那么只用记录以某个字母为结束点的最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void case467(string p){
	vector<int> dp(26,0);
    int n = p.size();
    int temp = 1;
    for(int i = 1;i<n;++i){
        if((p[i] == 'a' && p[i-1] =='z') || (p[i]-'a') == (p[i-1] - 'a' + 26 + 1)%26){
            // 连续
            temp++;
        }else{ // 不连续
            temp = 1;
        }
        dp[p[i]-'a'] = max(dp[p[i]-'a'], temp);
    }
    return accumulate(dp.begin(),dp.end(),0);
}

795. 区间子数组个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9

可以看到满足例题6， countArrayBetween， 可以使用 mostK(right) - mostK(left - 1)来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    std::function<int(vector<int>&, int)> atMostK = [&](vector<int>& nums, int k)->int{
            int ans = 0;
            int temp = 0;
            int n = nums.size();
            for(int i = 0;i<n;++i){
                if(nums[i] <= k){
                    temp++;
                }else{
                    temp = 0;
                }
                ans+=temp;
            }
            return ans;
        };
        return atMostK(nums, right) - atMostK(nums, left - 1);
}

904. 水果成篮

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
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。


提示：
1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length

就是给你一个数组， 让你选定一个子数组， 这个子数组最多只有两种数字，这个选定的子数组最大可以是多少。

和例题四一个样，只不过lessEqual判断为辨别可使用篮子的个数。采摘要连续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int totalFruit(vector<int>& fruits) {
	int n = fruits.size();
	unordered_map<int, int> mp;
	int j = 0; // 记录需要删除水果的起始下标
	int k = 2;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (mp[fruits[i]] == 0) { // 没使用过
			--k;
		}
		mp[fruits[i]]++;
		while (k < 0) {  // 有新水果进来，篮子已超出了两个
			// 直至删除空了一种水果，画图好理解
			mp[fruits[j]]--;
			if (mp[fruits[j]] == 0) {
				++k;
			}
			j++; 
		}
		ans = max(ans, i - j + 1);
	}
	return ans;
}

992. K 个不同整数的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。

示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：
输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].


提示：
1 <= nums.length <= 2 * 10^4
1 <= nums[i], k <= nums.length

条件为不同数字的个数。用个set，不断剔除掉最早出现的数字。

由例题 6，知：equalK = MostEqualK(k) - MostEqualK(k - 1)， 因此答案便呼之欲出了。其他部分和上面的题目 904. 水果成篮 一样。

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 subarraysWithKDistinct(vector<int>& nums, int k) {
	auto mostEqualK = [&](vector<int>& nums, int k)->int{
        unordered_map<int, int> mp;
        int j = 0; // 保存最早出现的数字
        int n = nums.size();
        int ans = 0;
        for(int i = 0;i<n;++i){
            if(mp[nums[i]] == 0){  // 没出现过，加进去
                --k; // 剩余的不同数目减一
            }
            mp[nums[i]]++;
            // 没出现过的数字加进去后发现超出了不同数字的要求值
            while(k<0){
                mp[nums[j]]--;
                if(mp[nums[j]] == 0){  // 直至清空前面任何一个数字
                    // 因为删除空的数字之前的那部分也是不能使用的，因为不连续
                    ++k; // k从-1归0， 此时正好用完
                }
                ++j;
            }
            ans += (i - j + 1);  // 按照之前求countArray的方法
        }
        return ans;
    };
    return mostEqualK(nums, k) - mostEqualK(nums, k-1);
}

1109. 航班预订统计

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
这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：
1 <= n <= 2 * 10^4
1 <= bookings.length <= 2 * 10^4
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // 差分数组
        vector<int> nums(n+1, 0);
        for(int i = 0;i<bookings.size();++i){
            nums[bookings[i][0]-1] += bookings[i][2];
            nums[bookings[i][1]] -= bookings[i][2];
        }
        for(int i = 1;i<n;++i){
            nums[i]+=nums[i-1];
        }
        nums.pop_back();
        return nums;
    }