arrays - 在小于 O(n^2) 的情况下生成给定数组的所有子数组的最快方法是什么？

Question

我想在一个数组中生成所有可能的子数组。我试过一个复杂度为 O(n^2) 的算法。

    for(i=1;i<=N;++i){
    if(S[i]==k)
      return 1;
    x=S[i];
    for(j=i+1;j<=N;++j){
        x^=S[j];
        if(x==k)
          return 1;
    }
}

Answer 1

从代码看来，您的函数试图:

Return 1 if there is a sub-array that XORs to a target value k, otherwise 0.

geeksforgeeks 中描述了一种更有效的解决方法:

An Efficient Solution solves the above problem in O(n) time. Let us call the XOR of all elements in the range [i+1, j] as A, in the range [0,i] as B, and in the range [0,j] as C. If we do XOR of B with C, the overlapping elements in [0,i] from B and C zero out and we get XOR of all elements in the range [i+1,j], i.e. A. Since A = B XOR C, we have B = A XOR C. Now, if we know the value of C and we take the value of A as m, we get the count of A as the count of all B satisfying this relation. Essentially, we get the count of all subarrays having XOR-sum m for each C. As we take sum of this count over all C, we get our answer.

那里的代码实际上更进一步，它返回具有目标值的子数组的总数，但是如果计数大于 0，您可以通过返回 1 来转换它以匹配您的问题。