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

有没有一种方法可以从其前缀和后缀和中找到初始序列？

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

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

最佳答案

前缀总和：

  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}

现在，找到原始序列：


如果原始数组具有n个元素，则组合数组将具有2 * n个元素
像array1 = {c [0]，c [2]，c [4]}和array2 = {c [1]，c [3]，c [5]}那样分割数组
现在array1将具有前缀和，而array2将具有后缀和
现在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];
}

关于java - 是否可以从其前缀和后缀和中找到整数的原始序列？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59651052/