LC2145.统计隐藏数组数目

image.png

思路：前缀和 + 计算距离

  • 利用前缀和计算出第一项不确定的数组hiden
  • 不全面的想法：hiden数组中，第0项为x，数字的范围集中在[x + minn]和[x + maxn]当中
  • 这个想法是我一开始的想法，但是实际上是不对的。因为minn和maxn的符号难以确定。

  • 允许的上下界范围是upper - lower可以将其视作一段距离，而hiden数组中允许的范围也可以视作一个距离。相减即可。

    代码：

    1. class Solution {
    2. public:
    3.   int numberOfArrays(vector<int>& differences, int lower, int upper) {
    4.       int begin_num = 0;
    5.       int n = differences.size();
    6.       vector<long long> nums(n + 1, 0);
    7.       for (int i = 1; i <= n; ++i) {
    8.           nums[i] = nums[i - 1] + differences[i - 1];
    9.       }
    11.       long long min_num = INT_MAX, max_num = INT_MIN;
    12.       for (int i = 1; i <= n; ++i) {
    13.           max_num = max(max_num, nums[i]);
    14.           min_num = min(min_num, nums[i]);
    15.       }
    17.       long long dis = max(max_num - min_num, max(abs(max_num - 0), abs(min_num - 0)));
    18.       return (upper - lower) - dis + 1 > 0 ? (upper - lower) - dis + 1 : 0;
    19.   }
    20. };