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 的子数组的每个子序列。

Answer 1

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

任意子数组

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

通过排序，最大的元素位于排序数组的末尾。通过对最大的元素求和即可得到最大的和。

That is what your code appears to do.

连续子数组

K 个相邻元素

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

计算第一个窗口的总和。

对于每个附加窗口:

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

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

任意数量的相邻元素

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