java - 是否可以从整数的前缀和和后缀和中找到原始整数序列？

Question

有没有办法从前缀和和后缀和中找到初始序列？

第 i 个位置的前缀和是从开始到第 i 个位置的所有元素的总和。

第 i 个位置的后缀总和是从最后一个位置到第 i 个位置的所有元素的逆序总和。

例如，组合(前缀和和后缀和)序列如下:

{1, 3, 3, 5, 6, 6}

初始序列为:{1, 2, 3}

前缀和:{1, 3, 6}，后缀和:{6, 5, 3}

组合起来:{1, 3, 3, 5, 6, 6}

在某些情况下可能有多种可能性。

Answer 1

前缀和:

<小时/>

  original array : {1, 2, 3}
  prefix sum array : {1, 1+2, 1+2+3}

后缀总和:

<小时/>

  original array : {1, 2, 3}
  suffix sum array : {3+2+1, 3+2, 3}

根据您的问题，组合数组似乎已排序。因此

<小时/>

 Let combined array be c[] = {1, 1+2, 3, 3+2, 1+2+3, 3+2+1} = {1, 3, 3, 5, 6, 6}

现在，找到原始序列:

1. 如果原始数组有 n 个元素，则组合数组将有 2*n 个元素
2. 拆分数组，如 array1 = {c[0], c[2], c[4]} 和 array2 = {c[1], c[3], c[5]}
3. array1 现在将具有前缀 sum，array2 将具有后缀 sum
4. 现在 array1 足以找到原始序列(因为组合数组已排序根据你的问题)。因此原始数组将是 {c[0], c[2]-c[0], c[4]-c[2]}

<小时/>

int length = combined_array.length/2;
int []prefix_breakup = new int[length];
int []original = new int[length];

for(int i=0; i<length ; i++){
    if( i%2 == 0 ){
        prefix_breakup[i] = combined_array[i];
    } 
}

original[0] = prefix_breakup[0];

for(int i=1; i<length ; i++){
    original[i] = prefix_breakup[i] - prefix_breakup[i-1];
}