我如何才能找到大小为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

我们可以这样做：

from itertools import combinations
from heapq import nsmallest
from math import factorial


arr = [2, 3, 2, 1, 1, 1, 1, 1, 2]
k = 3


def optimal(arr, k):
    if len(arr) < k:
        return 0

    k_smallest_elements = nsmallest(k, arr) # n * log(k)

    needed_count = k_smallest_elements.count(k_smallest_elements[k - 1]) 
    actual_count = arr.count(k_smallest_elements[k - 1])

    # Return actual_count Choose needed_count.
    return factorial(actual_count) // factorial(needed_count) // factorial(actual_count - needed_count)


def sub_optimal(arr, k):
    if len(arr) < k:
        return 0

    arr = sorted(arr) # n * log(n)
    needed_count = arr[:k].count(arr[k - 1])
    actual_count = arr.count(arr[k - 1])

    # Return actual_count Choose needed_count.
    return factorial(actual_count) // factorial(needed_count) // factorial(actual_count - needed_count)


def brute_force(arr, k):
    min_sum = sum(sorted(arr)[:k])
    return len([k_len_subset for k_len_subset in combinations(arr, k) if sum(k_len_subset) == min_sum])


count = optimal(arr, k)
assert count == sub_optimal(arr, k) == brute_force(arr, k) # Remove this line in production.
print(count)

Answer 2

一般来说，这个问题有两种变体。我将为这两个问题提供解决方案，以帮助未来的读者。您正在寻找任意子阵列的最小和（其他人可能需要最大和）（选择任意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）时间内计算出来。你知道吗