Brut Force“Subarray产品小于K”

Question

我试图使用递归来解决这个问题，获取所有连续的子数组，然后检查

给你一个正整数数组nums。计算并打印子数组中所有元素的乘积小于k的（连续）子数组的数量

此时我写了这部分代码:

def product_arr(array):
    counter = 1
    for i in range(len(array)):
        counter *= array[i]
    return counter


def numSubArray(array, k):
    if len(array) == 0:
        return 0
    if product_arr(array) <= k:
        return 1
    res_1 = numSubArray(array[1:], k//array[0])
    res_2 = numSubArray(array[:-1], k//array[-1])

    return 1 + res_1 + res_2

但它不起作用...它现在正在打印“15”而不是“8”，用于：

arr = [10, 5, 2, 6]
print(numSubArray(arr, 100))

感谢您抽出时间:)

Answer 1

如果你用简单的英语（或者你最熟悉的任何语言）拼出你认为递归关系是什么样子的，这通常会有所帮助，而且我有理由相信你的递归想法是错误的。你写的是这样的：

1. 在空数组中，没有子数组（但您返回无而不是0。为什么？
2. 如果数组中所有数字的乘积小于k，则子数组的数量为1。
3. 否则，如果我们删除第一项，则是子数组的数量，如果我们删除第二项，则加上子数组的数量。

这三点都有问题。首先，在1中，应该返回0而不是“nothing”。空数组没有连续子数组，因此“0”是正确答案。

现在来看第2行。您的＜code＞返回1

该逻辑的修复方法是：不返回1，而是返回'1 res1 res2'。

现在让我们来看看你的递归逻辑：

您说：“要计算给定数组的所有连续子数组，使其乘积小于 k，我们首先计算该数组中不包含数组第一个元素的所有连续子数组。然后，我们计算该数组中不包含数组最后一个元素的所有连续子数组。我们将这两个数字相加，最后，我们检查总数组的乘积是否小于或等于k，如果是这种情况，则加1。

递归逻辑的问题是您将重复计算数组“中间”的一些数组！它们既不包含第一个也不包含最后一个元素！

不过，你的思维方向是正确的！这种“除了第一个之外的一切”和“除了最后一个之外的一切”的递归在comp sci和数学中到处出现。诀窍是你需要稍微调整一下，以“强制”你的公式考虑第一个元素：

我们想要的是:给定我的数组，有多少个合适的连续子数组肯定包含第一个元素，但肯定不包含最后一个元素？以及有多少个连续的子数组肯定包含最后一个元素，但肯定不包含第一个元素？

您已经获得了“不包含第一个/最后一个”元素部分，以及数组索引。现在，我们如何“强制”它包含第一个元素？通过也将其从索引中删除并相应地调整k。

以下是我的意思的一个例子：

有多少个连续子阵列满足< code>[10，5，2，6]的条件，其中< code>k = 100，因此它们包含< code>10，但不包含< code>6？

与满足[5,2]条件且k=10的连续子数组一样多。基本上，通过从数组中删除10并将k除以10我们说：“哦，是的，我们肯定是在选择10，所以我们必须相应地调整k”。

因此，在递归中，在这两种情况下，它都将是数组[1:-1]和k，替换为k/array[0]或k/array[-1]（请确保选择正确的一个，并花一些时间思考整数除法和舍入，这是我留给您的练习：p）

这应该会让你很好地解决它，但是现在这里有一个额外的技巧来加快速度。快速问题，无需太多思考，[1,2,3,4,5，]的多少连续子数组的乘积小于1000？答案：所有。所以如果你先计算数组的乘积，并且它小于k，你就不需要再进行蛮力递归了！你“只”需要计算这些连续子数组的总数！根据你的背景，这是一个简单的组合问题。

编辑：再思考一下：）好的，让我们思考一下如何解决这个问题。首先，如果你真的想使用暴力，你只需要创建每一个可能的连续子阵列并检查其乘积：

count = 0
for start in range(0, len(array)):
  for end in range(start+1, len(array)):
    if product_arr(array[start:end]) <= k:
      count += 1

不幸的是，它的运行时间是O(N^3)，因为你实际上有三个嵌套循环。

这一切让我想起的是最大和邻接子阵列问题：https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

这可以用O(N)来解决，我认为一般的想法也可以用在这里，但是你不用跟踪最大值，而是跟踪“工作”的子阵列的数量，并且你以一种聪明的方式这样做...

您将运行一个具有“子数组的开始”的循环，然后在另一个具有“子数组的结束”的循环中运行。您不断将末尾增加1，并检查将该额外整数添加到产品中是否使您低于“k”。如果是这样，你继续前进，并通过“结束 - 开始1”增加你的子数组计数。这是加快速度的关键技巧。基本上，您不仅要计算一个新识别的子阵列，还要计算通过删除第一个，第二个，第三个元素等元素获得的所有其他子阵列。因为如果 a * b * c

这是一个有点棘手的数字边界和确切的细节，但我不能帮助你。