我们将如何测试数组中子数组的所有组合,其中
每个子数组的长度等于子数组元素总和的 P 倍。
一个简单的例子:
编辑:
A = [2,-1,3,0,1,2,1] , P =2
想要的结果:[2,-1] , [0,1]
编辑
约束:
N represents number of elements in an array
1 <= N <= 1e5
-1000 <= P <= 1000
|A[i]| <= 1e6
这些问题属于什么样的问题集(例如:NP-hard?)?语言:C#
最佳答案
这个问题属于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));
}
}
关于c# - 在数组中查找长度等于 P *(元素总和)的子数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69296597/