0

我正在尝试编写一个问题，我必须找到给定数组的连续子数组和给定的总和。我想要做的是使用一个从 0 到 n 的循环 i 和另一个从 i 到 n 的循环，并使用它计算所有子数组和。但我认为可以进一步降低解决方案的时间复杂度。我只是不知道怎么做。问题可以转化为 DP 吗？我需要找到子数组的总数。

4

1 回答 1

1 
For positive numbers only

将变量初始化curr_sum为第一个元素。curr_sum表示sum of current subarray. 从第二个元素开始，将所有元素一一添加到curr_sum. 如果curr_sum等于sum，则打印解决方案。如果curr_sum超过sum，则在curr_sum大于时删除尾随元素sum。

该算法将给出第一个正确答案。可能存在多个子数组作为答案。``

复杂性：O(n)

于 2013-07-03T06:58:30.957 回答