2145. 统计隐藏数组数目 - 力扣（LeetCode）
问题分析
已知 differences 数组表现隐藏数组相邻元素的差值，即 differences = hidden[i + 1] - hidden。
隐藏数组 hidden 的长度为 n + 1（n 是 differences 数组的长度），且全部元素的值在区间 [lower, upper] 内。
我们必要找到满足上述条件的隐藏数组的数量。
考点：前缀和
思路
记hidden数组为a，differences数组为d
题目中的等式可以简写为di = a[i+1] - a
也就是说a[i+1] = a + d
a1 = a0 + d0
a2 = a1 + d1 = a0 + d0 + d1
……
ai = a0 + (d0 + d1 + …… + di)
此时就可以利用前缀和思想将d数组的前缀和数组记为S，简化上述公式为ai = a0 + Si
也就是说，当a0确定后，ai就可以得到，那么就只必要通过[lower, upper]的约束条件确定公道的a0取值范围，a0的合法取值范围就是结果。因为a0合法的前提是a0在区间[lower, upper]中，且由a0确定的全部ai也在[lower, upper]区间中。
lower <= a0 + Si <= upper (0 <= i <= n)
<==> lower - Si <= a0 <= upper - Si (0 <= i <= n)
<==> lower - min_S <= a0 <= upper - max_S
最后的结果cnt就是区间内整数的个数 upper - max_S - （lower - min_S）+ 1
必要注意的是，存在不符合要求的数组时，区间内整数的个数是负数，必要和零求最大值再返回。
由于存在n == 10^5，differences == 10^5的情况，此时前缀和最后一项为10^5*10^5 = 10^10，必要用long long类型制止越界。在利用max函数的时候，必要确保比力的两个数据的类型必要一致，也就是都应该是long long型的，因此必要利用0LL。
代码
- class Solution {
- public:
- int numberOfArrays(vector<int>& differences, int lower, int upper) {
- long long s = 0, min_s = 0, max_s = 0;
- for (int d : differences) {
- s += d;
- min_s = min(min_s, s);
- max_s = max(max_s, s);
- }
- return max((upper - max_s) - (lower - min_s) + 1, 0LL);
- }
- };
复杂度
O(n)
学习
前缀和
思想
原数组：a1,a2,a3,……an
前缀和数组：Si = a1+a2+a3+……+ai
①如何求Si？ S = s[i-1]+a ，必要先给定S[0] = 0;
②作用？快速求出其中原数组区间[l, r]的和 → sum{a[l ~ r]} = S[r] - S[l-1]
前缀和中必要让下标从1开始，这是为了便于求解边界的值
比方想要求区间[1, 10]的和时候，其实就是S[10],为了可以统一全部的计算方式，酿成S[10]-S[0]，可以省去一次特判。
二维前缀和
S黄= S[x2,y2] - S[x1-1, y2] - S[x2, y1-1] + S[x1-1, y1-1]
- 如何求S[i, j]？
- for(i:1~n)
- for(j:1~m)
- S[i, j] = a[i, j] + S[i-1, j] + S[i, j-1] - S[i-1,j-1]
a1, a2, …… an是前缀和数组，构造b1, b2,……,bn差分数组，使得ai = b1 + b2 + …… + bi
和前缀和是逆运算
作用：将数组a的区间[l, r]都加上c，如果是直接举行计算的话复杂度是O(n)，但是在差分数组上做的话复杂度是O(1)，通过差分数组求数组a的时间复杂度是O(n)。虽然都有O(n)，但是其针对的情况是数组区间的加c操作是多次的，以是利用差分是更简单的。
如果给b[l]加c,相当于给a[l]+c，a[l+1]+c，a[l+1]+c，……，a[n]+c
此时给b[r+1]减c,相当于给a[r+1]-c，a[r+2]-c，……，a[n]-c
同时操作相当于给a[l]+c，a[l+1]+c，……，a[r] + c，也就实现了最初的目标给数组a区间[l, r]都加上c
二维差分
原数组a[i, j]，差分数组b[i, j]，就只必要使得a[i, j]是b[i,j]的前缀和即可
类比一维，相当于是给一个子矩阵加上c
b[x1, y1] += c; b[x1, y2+1] -= c; b[x2+1, y1] -= c; b[x2+1, y2+1] += c;
可能记载的思路存在不清楚，请体谅。欢迎各人在批评区交流沟通。
主要的解题思路参考了力扣题解区的灵茶山艾府，个人记载整理后加深一下印象和明白hh
如有侵权，接洽删帖~
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
