从 O(n) 中的数字序列中找到一个连续子序列的算法，其总和将是一个要求的数字 M

Question

假设我们有一个正数数组，并且给定了一个值 M。我们的目标是寻找正数数组中是否存在连续的子序列使得序列之和恰好等于和M。如果A[1],A[2],....A[n]是一个数组那么我们必须找到是否存在i 和 j 这样 A[i]+...+A[j] = M.

我正在尝试使用贪婪方法获得 O(n) 解。

Answer 1

（已编辑：参见 templatetypedef 的评论）

使用两个索引方法：如果子序列太小，则增加较低的索引，否则增加较高的索引。

示例：

void solve(int *a, int n, int M) {
    if (n <= 0) return;
    int i, j, s;
    i = 0, j = 0, s = a[j];
    while (j < n) {
        if (s == M) {
            printf("%dth through %dth elements\n", i + 1, j + 1);
            return;
        } else if (s < M) {
            j++;
            s += a[j];
        } else {
            s -= a[i];
            i++;
        }
    }
}

Answer 2

我相信你可以用指针追逐算法在线性时间内解决这个问题。

这是直觉。从数组左侧的指针开始。继续向右移动它，跟踪到目前为止你所看到的元素的总和，直到你恰好达到 M（完成！），你的总数超过 M（暂时停止，添加更多元素只会让情况变得更糟），或者你没有达到至少 M 就到达了数组的末尾（所有元素组合起来都太小了）。如果你最终遇到总和超过 M 的情况，你可以保证没有从数组开头开始的子数组加起来恰好是 M，因为你尝试了所有的子数组并且它们要么太小要么太大。

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

总的来说，每个指针最多前进 n 次，每一步的工作量为 O(1)，因此运行时间为 O(n)。另外，它仅使用 O(1) space，这已经很好了！

Answer 3

这是一个标准的二指针问题。首先，创建一个数组 prefix 来存储给定数组的前缀和，例如 arr.

所以

prefix[i] = arr[1] + .. + arr[i]

从两个指针开始，lower 和 upper。将它们初始化为

lower = 0
upper = 1

(注：初始化prefix[0]为0)

现在，试着理解这段代码：

lower = 0, upper = 1;
while(upper <= n) { // n is the number of elements
  if(prefix[upper] - prefix[lower] == m) {
    return true;
  } else if(prefix[upper] - prefix[lower] > m) {
    lower++;
  } else {
    upper++;
  }
}
return false;

这里我们利用数组由正整数组成的事实，因此 prefix 正在增加

Answer 4

假设索引 X ≤ i < Y 的子数组可能是解。

您从 X = 1、Y= 1、元素总和 = 0 开始。

只要总和小于M，且Y <= n，将总和增加数组[Y]，将Y替换为Y + 1。

如果总和等于M，则您找到了解决方案。

如果总和小于M，则删除开头的数组元素：只要总和大于M，就从总和中减去数组[X]并将X替换为X + 1。如果总和变得等于 M，你有一个解决方案。否则你从第一个循环开始。

Answer 5

public class FindSumEquals {

    public static void main(String[] args) {
        int n  = 15;
        System.out.println("Count is "+ findPossible(n));
    }

    private static int findPossible(int n) {
        int temp = n;
        int arrayLength = n / 2 + 2;
        System.out.println("arrayLength : " + arrayLength) ;
        int a [] = new int[arrayLength];
        int count = 0;
        for(int i = 1; i < arrayLength; i++){
            a[i] = i + a[i - 1];
        }
        int lower = 0, upper = 1;
        while(upper <= arrayLength - 1) {
            if(a[upper] - a[lower] == temp) {
                System.out.println("hello - > " + ++lower + " to "+ upper);
                upper++;
                count++;
            } else if(a[upper] - a[lower] > temp) {
                lower++;
            } else {
                upper++;
            }
        }
        return count;
    }
}

从 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)

arrays

algorithm

subset-sum