相关疑难解决方法(0)

给定一个输入数组,我们可以找到一个单个子阵列,它通过跟踪到目前为止找到的总和和起始位置,在线性时间内总和为K(给定).如果当前总和变得大于K,我们继续从起始位置移除元素,直到我们得到当前总和<= K.

我从geeksforgeeks找到了示例代码并更新了它以返回所有这些可能的集合.但假设输入数组仅由+ ve数组成.

bool subArraySum(int arr[], int n, int sum)
{
    int curr_sum = 0, start = 0, i;
    bool found = false;

    for (i = 0; i <= n; i++)
    {
        while (curr_sum > sum && start < i)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        if (curr_sum == sum)
        {
            cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"\n";
            curr_sum -= arr[start];
            start++;
            found = true;
        }

        // Add this element to curr_sum
        if (i < n) …

我在接受采访时遇到了以下问题,尽管我提供了一个有效的实施方案,但效率还不够高.

数组A的切片是任意一对整数(P,Q),使得0≤P≤Q<N.如果数字A [P] + A [P,则数组A的切片(P,Q)可被K整除+1] + ... + A [Q-1] + A [Q]可被K整除.

要求我写的函数必须返回被K整除的切片数.预期的时间复杂度为O(max(N,K)),空间复杂度为O(K).

我的解决方案是最简单的,一个循环在另一个内部并检查每个切片:O(n ^ 2)

我一直在想,但我真的无法弄清楚如何在O(max(N,K))中做到这一点.

它可能是子集求和问题的变体,但我不知道如何计算每个子数组.

编辑:数组中的元素可能是否定的.这是一个例子:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}