java - 如何找到数组中所有可能性的大小为 k 的子数组的总和？

Question

我已经用连续的子数组做到了这一点，但是要找到大小为 k 且每种可能性的子数组的总和是困难的，而且我一直面临死胡同。请帮帮我。

        for(int i=0;i<n;i++)
            {
                a[i] = sc.nextInt();
            }
            Arrays.sort(a);
            for(int j=0;j<k;j++)
            {
                sum = sum + a[j];
            }
        }
        System.out.println(sum);

这是我想要做的事情，以获得最小总和，但我不知道如何获得大小为 k 的子数组。

现在我想计算子数组大小和在数组中重复的次数。

例如：给定数组 [2, 5, 9, 7, 6, 3] 和长度为 k = 3 的子数组；比我们必须检查数组中的每个可能性总和，例如 [2, 5, 9] = 16; [2, 9, 7] = 18; [5, 6, 3] = 14...对每个数字检查大小为 k 的子数组的每个子序列也是如此。

标签： javapythonarraysalgorithmtime-complexity

Answer 1

一般来说，这个问题有两种变体。我将介绍两者的解决方案，以帮助未来的读者。您正在寻找任意子数组（选择任何 K 个元素）的最小总和（其他人可能想要最大总和）。另一个常见的类似问题是找到给定（选择 k 个相邻元素）或任意长度的连续子数组的最小或最大和。

任意子阵列

您可以在 O(n Log n) 时间内解决此问题。对子数组进行排序，然后对排序后的数组中的最后 k 个元素求和。

通过排序，最大的元素位于排序数组的末尾。通过对最大的元素求和，您可以获得最大的总和。

这就是您的代码似乎要做的事情。

连续子阵列

K个相邻元素

您可以通过计算数组中滑动窗口的总和在 O(n) 时间内解决此问题。第一个窗口由索引 0..(k-1) 处的元素和最后一个元素 (n-2)..n 组成。

计算第一个窗口的总和。

对于每个附加窗口：

• 该窗口的总和是前一个窗口的总和，减去刚刚掉出的元素（窗口开始下方的数组元素），并添加刚刚包含的元素（刚刚包含在当前窗口中的数组元素）窗户）。
• 取当前窗口总和的最小值或最大值（根据需要）和迄今为止记录的最高总和。这是您目前的最低或最高金额。

处理完最后一个窗口后，您的 min 或 max 变量代表最低或最高总和（视情况而定）。如果需要，您还可以在 max 更改时记录该窗口的起始索引。

任意数量的相邻元素

有趣的是，也可以使用称为Kadane 算法的巧妙方法在 O(n) 时间内计算任意长度子数组的最高和。