在数组中查找子数组，其长度等于P *（元素总和）。

Question

如何测试一个数组中所有子数组的组合，其中每个子数组的长度等于P乘以子数组元素之和。

一个简单的例子： 编辑：

 A = [2,-1,3,0,1,2,1] , P =2

期望结果：

1. 长度为2，P 乘以数组元素的和等于1。子数组包括 [2,-1]，[0,1]

编辑约束条件：

N represents number of elements in an array
1 <= N <= 1e5
-1000 <= P <= 1000
|A[i]| <= 1e6

这些问题属于什么类型的问题集（例如：NP-hard问题）？语言：C#

- user1907849

---

什么是约束？不要称子集为子数组（你需要子集） - MBo

或者您需要子数组（连续的片段）吗？示例显示子集。 - MBo

@MBo：我需要子数组。 - user1907849

{2，-1}和{-1,0,1,2}不是子数组。 - MBo

@MBo：是的，我已经相应地编辑了问题。 - user1907849

Answer 1

这个问题属于 P 类。这是一个 O(n) 的解决方案。

让我们用前缀和进行一些代数运算：

j - i = p * (prefix_sum_j - prefix_sum_i)
j - i = p * prefix_sum_j - p * prefix_sum_i
j - p * prefix_sum_j = i - p * prefix_sum_i
p * prefix_sum_j - j = p * prefix_sum_i - i

使用 JavaScript 编写代码并防范暴力破解攻击。

const f = (nums, p) =>
  nums.reduce(([map, sum, answer], val, i) => {    
    const newSum = sum + val;
    answer += p * newSum == i + 1;
    answer += map[p * newSum - i] || 0;
    map[p * newSum - i] = (map[p * newSum - i] || 0) + 1;
    return [map, newSum, answer];
  }, [{}, 0, 0])[2];


console.log('Input: [2,-1,3,0,1,2,1], 2')
console.log('Output: ' + f([2,-1,3,0,1,2,1], 2));


function bruteForce(A, p){
  let result = 0;

  for (let windowSize=1; windowSize<=A.length; windowSize++){
    for (let start=0; start<A.length-windowSize+1; start++){
      let sum = 0;

      for (let end=start; end<start+windowSize; end++)
        sum += A[end];
      
      if (p * sum == windowSize)
        result += 1;
    }
  }

  return result;
}


var numTests = 500;
var n = 20;
var m = 20;
var pRange = 10;

console.log('\nTesting against brute force...')

for (let i=0; i<numTests; i++){
  const A = new Array(n);
  for (let j=0; j<n; j++)
    A[j] = Math.floor(Math.random() * m) * [1, -1][Math.floor(Math.random()*2)];
  
  const p = Math.floor(Math.random() * pRange) * [1, -1][Math.floor(Math.random()*2)];

  _f = f(A, p);
  _brute = bruteForce(A, p);

  //console.log(String([_f, _brute, p, JSON.stringify(A)]));

  if (_f != _brute){
    console.log('MISMATCH!');
    console.log(p, JSON.stringify(A));
    console.log(_f, _brute);
    break;
  }
}

console.log('Done testing.')

如果有助于读者理解，函数 f 作为一个 for 循环可能如下所示：

function f(A, p){
  const seen = {}; // Map data structure
  let sum = 0;
  let result = 0;
  
  for (let i=0; i<A.length; i++){
    sum += A[i];
    result += p * sum == i + 1; // Boolean evaluates to 1 or 0
    result += seen[p * sum - i] || 0;
    seen[p * sum - i] = (seen[p * sum - i] || 0) + 1;
  }
  
  return result;
}

我第一次尝试使用C#编写的代码：

using System;
using System.Collections.Generic;

public class Solution{
  static int f(int[] A, int p){
    var seen = new Dictionary<int, int>();
    int sum = 0;
    int result = 0;
  
    for (int i=0; i<A.Length; i++){
      sum += A[i];
      result += Convert.ToInt32( p * sum == i + 1 );

      int key = p * sum - i;

      if (seen.ContainsKey(key)){
        result += seen[key];
        seen[key] += 1;

      } else {
        seen[key] = 1;
      }
    }
  
    return result;
  }


  public static void Main(){
    int[] A = new int[7]{2, -1, 3, 0, 1, 2, 1};
    int p = 2;

    Console.WriteLine(f(A, p));
  }
}

- גלעד ברקן

Answer 2

我尝试使用动态规划来解决这个问题。在我的解决方案中，我使用了两个嵌套的for循环来创建dp矩阵，因此它的时间复杂度应该为O(n^2)（不计算用于打印解决方案的3个嵌套for循环）。由于这个问题可以使用暴力方法和多项式时间的动态规划方法来解决，所以它的复杂度为P。

using System;

public class Program
{
    public static void Main()
    {
        int n = 7;
        int p = 2;
        int[, ] arr = new int[n + 1, n + 1];
        int[] nums = new int[]{2, -1, 3, 0, 1, 2, 1};
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                arr[i, j] = arr[i - 1, j - 1] + nums[j - 1];
            }
        }

        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= n; k++)
            {
                Console.Write(string.Format("{0} ", arr[j, k]));
            }

            Console.Write(Environment.NewLine);
        }

        Console.Write(Environment.NewLine + Environment.NewLine);
        for (int i = 1; i <= n; i++)
        {
            Console.WriteLine(string.Format("For length {0}:  ", i));
            for (int j = i; j <= n; j++)
            {
                if (p * arr[i, j] == i)
                {
                    Console.Write(string.Format("{0} {1}: ", (j - i + 1), j));
                    for (int k = j - i + 1; k <= j; k++)
                    {
                        Console.Write(string.Format("{0},", nums[k - 1]));
                    }

                    Console.Write(Environment.NewLine);
                }
            }

            Console.Write(Environment.NewLine);
        }

        Console.Write(Environment.NewLine);
    }
}

您可以在dotnetfiddle上测试此代码（这是我编写的第一个C#代码，因此可能还有一些优化可在代码中完成）。

- Yashawant