双周赛第70场:LeetCode:5972.统计隐藏数组的数目

浏览次数 : 次 2022-01-23

博文字数统计 : 1.8k字 | 阅读所需时长 : 7分

× 文章目录

1. 双周赛第70场：LeetCode：5972.统计隐藏数组的数目

双周赛第70场：LeetCode：5972.统计隐藏数组的数目
- 时间：2022-01-22
- 力扣难度：Meduim
- 个人难度：Meduim
- 数据结构：数组
- 算法：前缀和、差分、区间求和

双周赛第70场：LeetCode：5972.统计隐藏数组的数目

1. 题目描述

题目：原题链接
- 给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的隐藏数组相邻元素之间的*差值 *。
- 更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。
- 同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在闭区间 [lower, upper] 之间。
- 比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
  - [3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
  - [5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
  - [1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
- 请你返回符合要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。
- n == differences.length
- 1 <= n <= 10^5
- -10^5 <= differences[i] <= 10^5
- -10^5 <= lower <= upper <= 10^5
输入输出规范
- 输入：差分数组 differences，区间范围lower、upper
- 输出：符合要求的隐藏数组的个数
输入输出示例
- 输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
- 输出：4
- 解释：符合要求的隐藏数组为：
  - [-3, 0, -4, 1, 2, 0]
  - [-2, 1, -3, 2, 3, 1]
  - [-1, 2, -2, 3, 4, 2]
  - [0, 3, -1, 4, 5, 3]

2. 方法一：双指针 & 暴力求解

思路
- 本题要求解符合要求的隐藏数组的个数，最容易想到的就是从区间下限lower开始，遍历到其上限upper
- 在遍历过程中，计算差分数组当前的前缀和加上此时遍历的循环变量的值是否还在区间内，即表示隐藏数组的其中一个元素是否在区间内，如果在区间内，且计算到了差分数组的最终前缀和，就计数加一
- 如果中间某一次不在区间内，那就表示以本次循环的初始值为隐藏数组的第一个元素是不满足要求的，即跳过本次循环
- 具体而言，就是维护一个计数器变量count、两个指针变量num、start，start表示当前正在讨论的隐藏数组的首元素，num表示隐藏数组的当前元素，此外，再维护一个索引index，表示使用到了差分数组的第几个元素
- 双指针暴力解法的复杂度是 $O(n^2)$，由于本题的数据规模是10^5，平方级复杂度为10^10,，会发生TLE超时

题解：双指针

public int numberOfArrays(int[] differences, int lower, int upper) {
    if (differences == null || differences.length == 0) return 0;
    int n = differences.length;
    int index = 0; // 记录差分数组的索引
    int count = 0; // 记录个数
    int start = lower; // 记录隐藏数组的首元素
    for (int num = start; num <= upper; ) {
        // 前缀和
        num += differences[index];
        if (num < lower || num > upper) {
            start++;
            if (start > upper) break;
            num = start; // 新的首元素
            index = 0;
            continue;
        }
        index++;
        if (index == n) {
            count++;
            index = 0;
            num = start + 1; // 新的首元素
            start++; // 新的首元素
        }
    }
    return count;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$

3. 方法二：前缀和 & 区间逼近(夹逼法)

思想
- 由于暴力解法会超时，就需要思考过程中有哪些可以简化的地方
- 由于当隐藏数组的首个元素确定后，当前隐藏数组就唯一确定了，即将问题简化为求解hidden[0]的个数，而不再是求解隐藏数组中的每一个元素并判断是否在区间内(暴力法)
- 从数学的角度分析，我们可以发现对于隐藏数组中的元素 hidden[j]而言，其一定满足
  - $hidden[j] >= lower$
  - $hidden[j] <= upper$
  - $hidden[j] = hidden[0]+\sum_{i=0}^jd[i]$
- 因此，可以得到hidden[0]必须满足的条件，可以抽象为坐标轴和区间的概念，更加容易理解
  - $hidden[0] >= lower$
  - $hidden[0] >= lower - \sum_{i=0}^jd[i]$
  - $hidden[0] <= upper$
  - $hidden[0] <= upper - \sum_{i=0}^jd[i]$
- 为了确保一定同时满足这四个条件，则需要满足：
  - $hidden[0] >= Max(lower, lower - \sum_{i=0}^jd[i])$
  - $hidden[0] <= Min(upper, upper - \sum_{i=0}^jd[i]) $
- 这两个公式表示的含义就是，遍历整个差分数组，首元素要大于每一次(对应隐藏数组每一个元素)下界中的最大值，且小于上界中的最小值，不断缩小范围，区间逼近
- 此时，就会得到hidden[0]的取值上下界，即取值范围，如果下界大于上界，说明不存在符合要求的hidden[0]，返回0，否则就返回这个取值范围内的整数数字个数
- 注意：运算过程中，前缀和可能很大，超出 int，所以需要使用 long

题解：前缀和

public int numberOfArrays(int[] differences, int lower, int upper) {
    if (differences == null || differences.length == 0) return 0;
    int n = differences.length;
    long[] sum = new long[n];
    sum[0] = differences[0];
    // 前缀和
    for(int i = 1; i < n; i++) {
        sum[i] = sum[i-1] + differences[i];
    }
    // 上下界
    int left = lower, right = upper;
    for(int i =0; i < n; i++) {
        left = Math.max(left, lower - sum[i]);
        right = Math.min(right, upper - sum[i]);
    }
    if(left > right) return 0;
    return right - left + 1;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$，两次不嵌套的遍历，线性复杂度
- 空间复杂度：$O(n)$，前缀和数组
思考与优化
- 思考：现在的解法中，需要维护一个前缀和数组，即线性的空间复杂度，能否优化为常量空间，且两次遍历能否优化为一次遍历
- 优化
  - 实际上，因为我们只需要求首元素的取值范围，即在循环中不断选择新的上下界，实现区间逼近，所以我们只需要在求出前缀和的同时，记录边界即可，无需分开操作
  - 且根据公式可得，当前前缀和越小，下界(左边界)越大，而当前前缀和越大，上界(右边界)越小，因此，我们只需要在遍历的过程中，记录前缀和的最大最小值即可，然后在求区间范围
  - 具体而言：当前缀和小于0时，当前时刻的下界将大于lower，上界为upper；当前缀和大于0时，当前时刻的下界为lower，上界将小于upper

题解：前缀和优化

public int numberOfArrays(int[] differences, int lower, int upper) {
    if (differences == null || differences.length == 0) return 0;
    int n = differences.length;
    long sum = 0L, min = 0L, max = 0L;
    for(int i = 0; i < n; i++) {
        sum += differences[i];
        min = Math.min(min, sum);
        max = Math.max(max, sum);
    }
    int count = (int) Math.max(0, upper - max - (lower - min) + 1);
    return count;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$，一次遍历，线性复杂度
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-23 20:42:30
最后更新： 2022-02-20 13:34:08
本文标题： 双周赛第70场:LeetCode:5972.统计隐藏数组的数目
本文链接： https://chthollists.github.io/post/7e083e99.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！