在数组中查找长度等于 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#

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 代码进行了暴力测试。

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

如果它对读者有帮助，函数 ，f作为for循环可能如下所示：

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.')

我（第一次）尝试 C# 代码：

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;
}