8 篇博文 含有标签「前缀和」

1、题干​

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 106

2、思路1-暴力​

• 对 nums 升序排序，求前缀和
• 暴力查找不大于 queries[i] 的前缀和数量

3、代码​

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    let ans = queries.map(Number);
    for (let i = 0; i < queries.length; i++) {
        if (nums.at(-1) <= queries[i]) ans[i] = nums.length;
        else ans[i] = nums.findIndex((s) => s > queries[i]);
    }

    return ans;
};

4、复杂度​

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(\log{n})$

5、执行结果​

6、思路2-排序优化​

在思路1的基础上进行优化，如果 queries 是升序数组，那么查找子序列就不用每次都从头到尾遍历前缀和数组，可以从上一个找到的前缀和下标开始往后查找，查找过程复杂度从 $O(n^2)$ 降到 $O(n)$

7、代码​

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    const qs = queries.map((n, i) => [n, i]).sort((a, b) => a[0] - b[0]);

    let ans = queries.map(Number);
    for (let i = 0, j = 0; i < qs.length; i++) {
        if (nums.at(-1) <= qs[i][0]) {
            ans[qs[i][1]] = nums.length;
            continue;
        }

        while (nums[j] <= qs[i][0]) j++;
        ans[qs[i][1]] = j;
    }

    return ans;
};

8、复杂度​

• 时间复杂度： $O(n \log{n})$
• 空间复杂度： $O(n)$

9、执行结果​

1、题干​

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

• 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
  • 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
• 子数组是数组中的一个连续部分。

示例 1：

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i], k <= n
• nums 中的整数互不相同

整得有点复杂，错了几次，裂开

2、思路​

对于任意包含 k 的子数组符合要求的条件是：假设小于 k 的数有 cl个，大于 k 的数有 cr个，只要满足 cl === cr 或者 cl + 1 === cr 即可

以 k 的下标 ki 为界限，考虑三类子数组情况：

• 左半边子数组符合要求
• 右半边子数组符合要求
• 左右两边子数组组合后符合要求

前两类情况在 $O(n)$ 时间复杂度内可以出结果，第三类情况如果暴力求解，时间复杂度会达到$O(n^2)$，用哈希表优化可以做到 $O(n)$

3、代码​

function countSubarrays(nums: number[], k: number): number {
    const ki = nums.indexOf(k), om = new Map(), em = new Map();
    let ans = 0, sum = 0;
    for (let i = ki - 1; i > -1; i--) {
        sum += nums[i] < k ? -1 : 1;
        if (!sum || sum === 1) ans++;

        const map = i % 2 ? om : em;
        map.set(sum, (map.get(sum) || 0) + 1);
    }

    sum = 0;
    for (let i = ki + 1; i < nums.length; i++) {
        sum += nums[i] < k ? -1 : 1;
        if (!sum || sum === 1) ans++;

        let map = i % 2 ? om : em;
        if (map.get(-sum)) ans += map.get(-sum);

        map = i % 2 ? em : om;
        if (map.get(1 - sum)) ans += map.get(1 - sum);
    }

    return ans + 1;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：

• answer.length == nums.length
• answer[i] = |leftSum[i] - rightSum[i]|

其中：

• leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
• rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。

返回数组 answer 。

示例 1：

输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。

示例 2：

输入：nums = [1]
输出：[0]
解释：数组 leftSum 为 [0] 且数组 rightSum 为 [0] 。
数组 answer 为 [|0 - 0|] = [0] 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 105

2、思路​

计算前缀和与总和，遍历求得结果

3、代码​

function leftRigthDifference(nums: number[]): number[] {
    const sum = nums.reduce((a, c) => a + c, 0);

    for (let i = 0, ls = 0; i < nums.length; i++) {
        ls += nums[i];
        nums[i] = Math.abs(ls - nums[i] - (sum - ls));
    }

    return nums;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

示例 2:

输入: ["A","A"]

输出: []

提示：

• array.length <= 100000

2、思路​

• 遍历数组 array 并计算前缀和 sum，遇到字母 sum+1 否则 sum-1
• 如果当前 sum 的值从未出现过，将 sum 与下标 i 分别作为键值存入哈希表 map
• 如果当前 sum 的值已出现过，则 [map.get(sum)+1,i+1) 区间的子数组作为备选答案
• 最后取左下标最小的最长子数组

3、代码​

function findLongestSubarray(array: string[]): string[] {
    let sum = 0, l = 0, r = 0;
    const map = new Map([[0, -1]]);

    for (let i = 0; i < array.length; i++) {
        sum += (/[a-z]/i.test(array[i]) ? 1 : -1);
        const j = map.get(sum);

        if (j === undefined) map.set(sum, i);
        else if (i - j > r - l) r = i, l = j;
    }

    return array.slice(l + 1, r + 1);
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例  4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

前缀和，我是真的前了
哈希表，我是真的哈了
模运算，我模xxxxxxxxx了

2、思路​

先求 nums 前缀和数组 sums，数组总和 sum，总和与 p 的余数 mod，然后讨论几种情况:

• 无需剔除：如果 mod 为 0，返回 0
• 剔除1个：如果剔除 nums 中某个数能整除，返回 1
• 剔除尾部：如果 sums[i] 能整除 p，nums.length - i - 1 作为备选答案
• 剔除头部：如果 sums[i] % p === mod，i+1 作为备选答案
• 剔除中间：如果存在下标 i 和 j 且 sums[j] % p ===(sums[i] % p + p - mod) % p，i-j 作为备选答案

真是不知道写了个什么妖魔鬼怪

3、代码​

function minSubarray(nums: number[], p: number): number {
    const sums = [...nums];
    for (let i = 1; i < sums.length; i++) {
        sums[i] += sums[i - 1];
    }

    const sum = sums.at(-1), mod = sum % p;
    if (!mod) return 0;

    let ans = nums.length;
    const map = new Map();
    for (let i = 0; i < sums.length; i++) {
        if ((sum - nums[i]) % p === 0) return 1;

        const m = sums[i] % p;
        if (m === 0) ans = Math.min(nums.length - i - 1, ans);
        else if (m === mod) ans = Math.min(i + 1, ans);
        else {
            const sm = (m + p - mod) % p;
            if (map.has(sm)) ans = Math.min(i - map.get(sm), ans);
        }

        map.set(m, i);
    }

    return ans === nums.length ? -1 : ans;
}

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

• 1 <= hours.length <= 104
• 0 <= hours[i] <= 16

2、思路-前缀和+哈希表​

• 计算 hours 的前缀和数组 sums，当 hours[i] 大于 8 时前缀和 +1 否则 -1
• 将 sums[i] 与 i 分别作为键值存入哈希表 map；为保证结果时段最大，仅当哈希表中不存在 sums[i] 时才存入该键值对
• 如果 sums[i] 大于 0，则区间 [0,i] 可能是最长时段
• 如果 sums[i] 小于等于 0，则区间 [map.get(sums[i] - 1),i) 也可能是最长时段
• 所有备选时段长度的最大值即所求的最长时段

这题的前缀和在整数范围上具有连续性，所以能用哈希表

3、代码​

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const map = new Map();

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        else {
            if (map.has(sums[i] - 1)) ans = Math.max(ans, i - map.get(sums[i] - 1));
        }

        if (!map.has(sums[i])) map.set(sums[i], i);
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

6、前缀和+栈​

这个思路是我能写出来的吗

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const minStack = [0];

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        if (sums[i] < sums[minStack.at(-1)]) minStack.push(i);
    }

    for (let i = hours.length - 1; i > -1; i--) {
        while (sums[minStack.at(-1)] < sums[i]) {
            const l = minStack.pop();
            ans = Math.max(ans, i - l);
        }
    }

    return ans;
};

1、题干​

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

2、思路​

• 数组总和 sum 必须大于 x
• 找 x 转换为找 sum-x，会简单些
• 滑动窗口找总和为 sum-x 的区间 $(l, r]$，区间求和使用前缀和减少时间复杂度

3、代码​

function minOperations(nums: number[], x: number): number {
    let sum = 0, preSums = [];
    for (const n of nums) {
        sum += n;
        preSums.push(sum);
    }

    if (sum <= x) return sum < x ? -1 : nums.length;

    x = sum - x;
    let ans = Infinity, l = -1, r = 0;
    while (l <= r) {
        const y = preSums[r] - (preSums[l] ?? 0);
        if (y === x) ans = Math.min(nums.length - r + l, ans);
        y <= x ? r++ : l++;
    }

    return ans < Infinity ? ans : -1;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

• 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。

请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1:

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

提示：

• 3 <= s.length <= 105
• s 只包含字符 '*' 和 '|' 。
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= lefti <= righti < s.length

2、解题思路​

按题目意思要查找任意区间 [i,j] 内两支蜡烛之间的盘子数量，要解决两个核心问题：

• 1、查找区间 [i,j] 内最左边和最右边蜡烛的下标 [l,r]
• 2、求出区间 [l,r] 内的蜡烛数量

问题1采用区间映射解决，使用二维数组 ranges 存储离任意下标 i 最近的左右蜡烛下标，形如 ranges[i] = [li,ri]。对于任意区间 [i,j] 内最左边和最右边蜡烛的下标为 l = ranges[i][1], r = ranges[j][0]

特殊情况 :

• 左边没有蜡烛时有 ranges[i] = [-1,ri]
• 右边没有蜡烛时有 ranges[i] = [li,s.length]
• 该位置是蜡烛时有 ranges[i] = [i,i]

问题2采用前缀和解决，使用数组 sumList 存储蜡烛数量前缀和，对于任意下标 i 而言 sumList[i] 表示 s[0] 到 s[i] 之间的蜡烛数量。对于任意区间 [l,r] 内的蜡烛数量为 sumList[r] - sumList[l]

至此两个核心问题都得以解决，且都能在 $O(1)$ 时间复杂度内求出正解

3、代码​

var platesBetweenCandles = function (s, queries) {
    const n = s.length, sumList = new Array(n), ranges = new Array(n);
    let ps = 0, range = [-1, n];

    for (let i = 0; i < n; i++) {
        if (s[i] === '*') {
            ps += 1;
            ranges[i] = range;
        } else {
            range[1] = i;
            ranges[i] = [i, i];
            range = [i, n];
        }

        sumList[i] = ps;
    }

    return queries.map(([i, j]) => {
        const l = ranges[i][1], r = ranges[j][0];
        return l > -1 && r < n && l < r ? sumList[r] - sumList[l] : 0;
    });
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

• 执行用时: 308 ms
• 内存消耗: 86.1 MB