问题标签 [prefix-sum]

我想知道是否有更好的方法来为数组的部分和生成性能更好的解决方案。

给定一个数组 say x = [ 0, 1, 2, 3, 4, 5 ]，我生成了项目的子数组，然后计算每个数组的总和，得到：

所以完整的代码是：

我想知道平面地图或其他一些数组方法是否会有不需要扩展每个子数组的解决方案。

我们必须找到一个索引'x'，使得两者之间的绝对差异

(A[1]+A[2]+..+A[x]) 和 (A[x+1]+A[x+2]+..+A[n]) 对于某些 x ，

被最小化。

我偶然发现了这个帖子。

在这里，作者要求最小化子数组的产品，所以在我的问题中，我可以取数组元素的对数，问题结果与我所问的相同

我正在考虑计算前缀和数组并对其执行二进制搜索。但数组元素最多可达 10^19，存储总和可能会产生内存限制错误。

是否可以在 Kotlin 的 O(n) 时间内以纯函数式编程风格计算数组的所有前缀和？

我所说的纯函数式编程的意思是允许仅对集合使用函数式编程扩展函数，例如_Collections,ktmap中的,reduce​​ , fold,sum等，而传统的命令式编程方法涉及更改状态和可变数据，例如普通循环，又名可变变量s，并且不允许使用可变数组。（我认为这符合维基百科上的定义）var

更具体地说，这里是我想要实现的一个例子，它是用在 O(n) 时间内运行的命令式编程编写的，另一个是在 O(n^2) 时间内运行的函数式编程。

我正在解决问题Minimum Size Subarray Sum。我试图通过对前缀和数组使用二进制搜索来解决它，该数组解决了 n*log(n) 复杂性中的问题。

我设法让它工作，但我不明白为什么我的解决方案有效。

思考过程

我的思考过程如下：

• 第 1 步：给定原始数组 nums，首先我创建一个前缀和数组，如下所示：

• 第 2 步：然后我应用以下逻辑：

• 第 3 步：我遍历 prefix[] 数组 - 这表示prefix[r]. 由于nums具有所有正值，因此prefix数组总是在增加 - 即它是排序的。然后我使用二进制搜索prefix来查找prefix[l-1]满足上述属性的值 where tgt >= prefix[l-1]。

代码

我的代码如下：

这不起作用。因此，我对前缀数组进行了以下更改，使其以 0 开头：

我编辑了计算子数组的方式来解释这些变化：

我的算法现在奏效了。

我的问题

1. 我真的不明白这里发生了什么。为什么我的初始代码不起作用，为什么当我更改前缀和数组时它起作用？

2. 如果我想使用原始前缀和数组（即不以 0 开头的数组），我需要对我的算法进行哪些更改

我正在研究Sum at Least K 的 Shortest Subarray问题，其中最佳解决方案使用双端队列。

由于数组可以同时具有正值和负值，因此使用双指针技术将不起作用。我理解为什么 2 指针技术不起作用。

我对使用双端队列的最佳解决方案的理解如下：

• 在此解决方案中，最短子数组的所有可能起始值都保存在双端队列中。
• 双端队列存储数组的前缀总和值，以便我们可以在恒定时间内计算起始元素和当前元素之间的总和。
• 双端队列是单调递增的，因为如果我们有一个prefix = [a, b, c]and prefix[b] < prefix[a]then(c-b) > (c-a)和 since[b,c]小于[a,b,c]双端队列是单调递增的。

总和至少为 k 的最短子数组的代码如下：

我想我理解为什么这个特定的解决方案有效，但是我仍然对何时可以使用双端队列来优化滑动窗口问题感到困惑。

我的问题

我开始思考如果问题是找到总和至少为 K 的最长子数组而不是最短子数组会发生什么变化。

1. 如果我将问题更改为需要找到总和至少为 K 的最长子数组，我还能以类似的方式使用双端队列吗？
2. 如果可以使用双端队列，解决方案会是什么样子？你如何解释所有不同的起始位置？我们可以尝试将其设为单调递减队列，但我认为这不能解决问题。
3. 如果不能使用双端队列在 O(n) 时间内解决问题，那么有人可以给我一个令人信服的论据，说明为什么不能使用双端队列在 O(n) 时间内解决问题吗？

谢谢。

给定一个整数列表。

我想知道是否可以在每个查询的 O(1) 和前提的 O(n) 的段上计算按位或？（一些前缀和）（对于每个查询的 O(log n) 和前提的 O(n log n) 很容易做到这一点，例如，使用段树，但什么更快？）

问题陈述如下 - 给定一个整数数组，返回所有对中的第 k 个最小距离。一对 (A, B) 的距离定义为 A 和 B 之间的绝对差。

leetcode 接受的解决方案是 Binary Search + Prefix Sum Approach。但即使经历了100多次，我也无法弄清楚。

有人可以指导我吗？可能通过一个示例的空运行帮助我弄清楚我们是如何使用二分搜索实际消除搜索空间的？请帮我举个例子，因为互联网上有大量的描述性解释

我试图理解以下代码背后的逻辑，但是我不清楚代码的 2 部分，因为目前支持逻辑的数学对我来说并不完全清楚。

1. 困惑 1：我不明白为什么我们要在开始查找数组的总和之前将 0 和 count = 1 放在地图中？它有什么帮助？

2. 困惑 2：如果我map.put(sum, map.getOrDefault(sum)+1)在 if() 条件之后移动，我会得到正确的解决方案。但是，如果我把它放在下面代码所示的地方，它会给我错误的结果。问题是为什么这个位置很重要，当我们在地图中搜索 sum-k 的值以找到计数时

问题：https ://leetcode.com/problems/matrix-block-sum/

我正在尝试使用 2D 前缀总和来解决它，其中sum[i][j]是左侧所有元素的总和，包括元素及其行和列。

代码 ：

我正在解决一个LeetCode 问题：将所有球移动到每个盒子的最小操作数。

你有n盒子。你会得到一个长度为 的二进制字符串 box ，如果第一个盒子是空的，则为 '0'，如果它包含一个球，则为 '1 n' boxes[i]。i在一次操作中，您可以将一个球从一个盒子移动到一个相邻的盒子。返回一个大小为 的数组答案n，其中answer[i]是将所有球移动到第ith 个盒子所需的最小操作数。对于输入boxes = "001011"，输出为：[11,8,5,4,3,4]。

做到这一点O(n^2)是微不足道的。我只能这样解决。我试图理解这个 O(n)解决方案，但很难：

有人可以详细说明背后的逻辑：

我知道count每当遇到球时我们都会增加，但是如何left[i] = left[i - 1] + count;帮助我们计算到目前为止将左侧的所有球移动到所需的操作次数i（反之亦然right）？

谢谢！