连续子集数组Sum为某整数算法

Question

这里是问题所在：

给定一个包含 n 个整数的数组 A、一个单独的整数 M 和一个整数 d。求A的一个连续子数组S，使得子数组的大小小于等于d，S中所有元素的和为M。ReturnA的左右索引的索引子数组 S。所有数字都是正数。

如果有多个结果，给出最右边的结果。

我们必须在比 O(n^2) 或 O(n*d) 更短的时间内完成算法运行。所以基本上它必须是 O(nlog(n))，分而治之我假设是要走的路。我知道如何做最大连续子数组问题，但这变得更容易，因为当你分而治之时，你可以寻找最大子数组，有了这个你真的不知道你在子数组中寻找什么，如果这是有道理的，因为解决方案可能来自具有小数字的子数组和具有大

的子数组的组合

任何帮助我找到解决方案的人都将不胜感激！

在这一点上，我大约有 80% 的把握认为这是不可能的...我一直在研究它，但我想不出一种方法来完成这项工作，这是否可能是一个巨大的把戏问题？

Answer 1

如果 A 中的整数 >= 0，这就相对容易了，因为您可以只维护几个定义总和接近 M 的区间的指针，然后沿着数组从右向左滑动它。您是否有可能在问题中遗漏了一些像这样的额外信息？

好的 - 这是一些扩展。你有一个左指针和一个右指针。将右手指针从右向左移动，保持左手指针距右手指针不超过d个位置的不变式，且两个指针所围元素之和为最大可能数<= M。重复将右手指针向左移动一步并将左手指针向左移动，直到达到 d 的极限或进一步移动它会产生总和 > M。每次移动指针时，您可以递增或递减到维护两个指针所包含的总和的运行总和。

因为每次移动右手指针时数字 >= 0，总和就会减少或保持不变，所以您总是希望左手指针保持不变或将其向左移动。因为数字 >=0 你知道如果从右手指针位置开始有答案你会在左手指针位置找到它 - 任何没有延伸到左手指针太小的东西，任何进一步延伸的东西都太大了，除非有零的情况，在那种情况下你会找到一个解决方案，只是还有其他解决方案。

每个指针只在一个方向上移动，所以指针移动的最大次数是O(n)，每次指针移动的成本是固定的，所以复杂度是O(n)

Answer 2

如果所有数字都是非负数，这有一个 straightforward O(N) 解。 length<=d 的要求不会增加任何复杂性，只需添加一个检查 current_length<=d。我假设数组中有负数。我们需要额外的 O(N) space.

计算S的每个索引的前缀和：p(i) = sum(S,0,i)。将 p(i) 放入另一个数组 P 中：P[i]=p(i).
复制 P：PSorted = P。使用 stable 排序算法对 PSorted 进行排序。我们将其用作地图 prefix-sum -> index，索引是决胜局。
对于 S 的每个索引 k，从最大的开始：
- 设置p = P[k].
- 使用二分查找在 PSorted 中查找 p-M，偏右。假设结果索引是 q.
- 如果找到，并且q-k<d，return答案(k,q)。

这总体上 O(n log n) 复杂。

如果使用散列 table 而不是排序数组，预期运行时间可以减少到 O(N)，但需要注意总是 return 最右边 索引小于当前索引。

Answer 3

算法正确，时间复杂度为 O(n)，如果您仔细计算操作次数。

 public void SubArraySum(int[] arr, int d, int sum)
        {
            int n = arr.Length-1;
            int curr_sum = arr[0], start = 0, i;
            /* Add elements one by one to curr_sum and if the curr_sum exceeds the
               sum, then remove starting element */
            for (i = 1; i <= n; i++)
            {
                // If curr_sum exceeds the sum, then remove the starting elements
                while (curr_sum > sum && start < i - 1)
                {
                    curr_sum = curr_sum - arr[start];
                    start++;
                }

                // If curr_sum becomes equal to sum, then return true
                if (curr_sum == sum && Math.Abs(start - i - 1) <= d)
                {
                    Console.WriteLine("Sum found between indexes {0} and {1}", start, i - 1);
return;
                }

                // Add this element to curr_sum
                if (i < n)
                    curr_sum = curr_sum + arr[i];
            }

            // If we reach here, then no subarray
            Console.WriteLine("No subarray found");
        }

希望对您有所帮助:)

连续子集数组Sum为某整数算法

Consecutve Subset Array Sum is a certain integer algorithm

arrays

algorithm

dynamic-programming