查找数组中长度等于P *(元素之和)的子数组

Question

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

一个简单的例子:编辑:

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

预期的结果:

1. Length = 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代码

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

我尝试用动态规划来解决这个问题。在我的解决方案中，我使用了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#代码，所以也许在代码中可以做一些更多的优化)。