总和小于或等于给定“k”的子阵列数
我知道一个O（n2）soln，它能以更好的方式实现吗，因为数组中元素的数量限制非常大
共有3个答案
Outflak解释了问题的线性时间解的算法，前提是元素非常好地非负。
我带着与OP相同的问题来到这里，在阅读了Outlak的答案后得到了答案，但由于没有代码，我不得不自己写出来。
因此，我将添加一些Python代码，并对未来的读者进行一些解释：
left, right, runSum, count = 0, 0, 0, 0
nums = [10,11,30,1009,13]
limit = 35
# Expected answer - 5 ([10], [11], [10,11], [30], [13])
while right < len(nums):
runSum += nums[right]
while runSum > limit:
runSum -= nums[left]
left += 1
count += right - left + 1
right += 1
print(count)
>>> 5
只是重申一下：
>
在每一步，我们通过添加Nums[right]到runSum来扩展窗口。
然后，只要runSum大于允许的限制，我们就通过从窗口左侧减去来缩小窗口，即nums[left]
最后，right-left 1给出了当前有效窗口的“大小”，我们在每一步都将其添加到计数中。
正如shole所指出的，如果所有元素都是非负的，您确实可以使用“两个指针”技术来解决O（n）中的这个问题。
基本上你有两个指针左和右，都初始化为0。增加右指针，并跟踪当前和：而滑动窗口内的当前和是
是的，如果所有元素都是非负的，就有一个O（n lgn）算法。
- 定义
p[i]为p[0..i]（我们称之为前缀和） - 对于每个
i：二进制搜索最大值j，以便p[j]-p[i-1]
总的复杂度是O（n）O（n lgn）=O（n lgn）
为什么它工作，是因为对于每个i，我们试图找到从i开始的最大范围，使得该范围的总和为
让这个范围为[i..j]，因为所有元素都是非负的，所以[i..i]，[i..i 1]，[i..i 2]。。。[i..j]都是和为
我们为每个i找到这样的范围，并不断添加从i开始的子数组的数量，其中
-
给定一个（未排序的）数组S和一些整数k，找到对的数量i， j使得S的范围[i... j] 我在一次采访中收到了这个问题，经过排序后只能得出一个O（nlogn）解。但是，有人告诉我有一个O（n）解。有什么想法吗？
-
我在一次采访中遇到了以下问题。 给定一个数组，您需要找到所有元素小于给定值 k 的子数组 ，例如 现在，值小于 4 的子数组是： 注意｛4｝是如何重复的，但没有考虑两次。现在，代码应该返回不同子阵列的计数 在本例中为3. 另一个示例： 不同的子阵列: 我的方法是找到小于给定值k（即O（n^2））的子阵列，然后将其插入类似无序集的内容中以删除重复项。 有没有解决这个问题的有效方法？
-
Q） 给定阵列A1、A2…an和K计数，有多少子阵列的反转计数大于或等于K.N 所以，我在一次面试中碰到的这个问题。我想出了一个简单的解决方案，用两个for循环(O(n^2)形成所有子数组，并使用O(nlogn)的改进merge sort对数组中的逆序进行计数。这导致了O(n^3logn的复杂性)，我想这是可以改善的。有什么我可以改进的方法吗？谢谢！
-
我有一个大小为的整数值数组和一个给定的。 我想找到子序列的总数，使得每个子序列的元素总和小于。例如：设 ，，数组的元素为 ，则其总子序列为 作为- 但是，所需的子序列是: 也就是说，不被取，因为它的元素和是，这大于，即
-
我想找到给定正整数数组中元素的最大数目，使得它们的和小于或等于给定的k。例如，我有一个数组 答案是3，因为1，2，3是求和6的最大元素。
-
给定一个数组形式的未排序（多）整数集，求其和大于或等于常量整数x的最小基数子集。 我们的集合是{4 5 8 10 10}，x=15，所以最小基数子集和 这个问题与以下问题相关但不同：给定一个n个整数的列表，找到大于X的最小子集和在前面的问题中，作者要求得到一个和最接近X的子集，这里我们想要任何子集