从O（n）中的数字序列中找到一个总和为被问数字M的连续子序列的算法 [英] Algorithm to find a consecutive sub-sequence whose sum would be a asked number M from a sequence of numbers in O(n)

问题描述

我已经尝试解决这个问题已有一段时间了。
假设我们有一个正数数组，并且给我们一个值M。那么我们的目标是查找正数数组中是否存在连续的子序列，使得该序列的总和完全相等求和M。如果A [1]，A [2]，.... A [n]是一个数组，那么我们必须找出是否存在i和j，使得A [i] + ... + A [ j] =M。我正在尝试使用贪婪方法获得O（n）解。

Hi I have been trying to solve this problem for some time now. Lets say we have an array of positive numbers and we were given a value M. Then our goal is to find if there is a consecutive sub sequence in the array of positive numbers such that the sum of the sequence is exactly equal to sum M. If A[1],A[2],....A[n] is an array then we have to find if there exist i and j such that A[i]+...+A[j] = M. I am trying to get the O(n) solution using greedy approach.

推荐答案

我相信您可以解决

这是直觉。从数组左侧的指针开始。继续将其向右移动，跟踪到目前为止所见元素的总和，直到精确地达到M（完成！），总和超过M（暂时停止，添加更多元素只会使情况更糟），否则，您到达数组末尾而未达到至少M个（合并的所有元素都太小）。如果您确实在总和超过M的情况下结束运算，则可以保证从数组开头开始的子数组不会合计为M，因为您尝试了所有子数组，而它们太大或太小。

Here's the intuition. Start off a pointer at the left side of the array. Keep moving it to the right, tracking the sum of the elements you've seen so far, until you either hit exactly M (done!), your total exceeds M (stop for now, adding in more elements only makes it worse), or you hit the end of the array without reaching at least M (all the elements combined are too small). If you do end up in a case where the sum exceeds M, you can be guaranteed that no subarray starting at the beginning of the array adds up to exactly M, since you tried all of them and they were either too small or too big.

现在，在第一个元素处开始第二个指针，并继续向前移动，减去当前元素，直到精确到M（完成！），到达第一个指针（暂时停止），或总下降到M以下（暂时停止）。您用此指针跳过的所有元素都不是您要查找的子数组的起点。此时，再次开始将第一个指针向前移动。

Now, start a second pointer at the first element and keep advancing it forward, subtracting out the current element, until you either get to exactly M (done!), you reach the first pointer (stop for now), or the total drops below M (stop for now). All the elements you skipped over with this pointer can't be the starting point of the subarray you're looking for. At this point, start marching the first pointer forward again.

总体而言，每个指针最多前进n次，并且每步执行O（1）工作，因此运行在时间O（n）中。另外，它仅使用O（1）空间，这将与它得到的一样好！

Overall, each pointer advances at most n times and you do O(1) work per step, so this runs in time O(n). Plus, it uses only O(1) space, which is as good as it's going to get!

这篇关于从O（n）中的数字序列中找到一个总和为被问数字M的连续子序列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！