给定一个仅包含整数和奇数和的数组 arr[]。目标是创建一个和数组 arr_2[],这样每个 arr_2[i] 是 arr[] + arr[i] 的前 sum/2 个元素的总和 + arr[] 的下一个 sum/2 个元素。如果 sum 为 1,则 arr_2[i]=arr[i]
例如
arr[] = { 4, 1, 7, 5, 2, 9} sum=3输出结果
Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3
The sum array is constructed as: arr_2[0]=arr[0]+arr[1] = 4+1 = 5 arr_2[1]=arr[0]+arr[1]+arr[2] = 4+1+7 = 12 arr_2[2]=arr[1]+arr[2]+arr[3] = 1+7+5 = 13 arr_2[3]=arr[2]+arr[3]+arr[4] = 7+5+2 = 14 arr_2[4]=arr[3]+arr[4]+arr[5] = 5+2+9 = 16 arr_2[5]=arr[4]+arr[5] = 2+9 = 11s
arr[] = { 1,2,3,4,5 } sum=5输出结果
Construction of sum-array with sum of elements in given range are − 6 10 15 14 12
The sum array is constructed as: arr_2[0]=arr[0]+arr[1]+arr[2] = 1+2+3 = 6 arr_2[1]=arr[0]+arr[1]+arr[2]+arr[3] = 1+2+3+4= 10 arr_2[2]=arr[0]+arr[1]+arr[2]+arr[3]+arr[4] = 1+2+3+4+5 = 15 arr_2[3]=arr[1]+arr[2]+arr[3]+arr[4] = 2+3+4+5= 14 arr_2[4]=arr[2]+arr[3]+arr[4]= 3+4+5 = 12
以下程序中使用的方法如下-
在这种方法中,我们将使用滑动窗口的概念。将下一个最右边的元素添加到前一个窗口总和并从中删除最左边的元素。
以整数数组 arr[] 和值 sum 作为输入。
函数 sum_array(int arr[], int size, int sum) 返回给定范围内元素总和的总和数组。
取初始计数为 0。
取 sum 数组为 arr_2[size]。
取温度 = sum / 2 + 1。
将 temp 元素从 0 的数量添加到 temp 以进行计数。并将 arr_2[0] 设置为计数。
对于 sum 数组的下一个元素,使用 for 循环从 i=1 遍历到 i<size。
取 temp_1 = i − (sum / 2) − 1。如果 >=0,则从计数中减去 arr[temp_1]。
取 temp_2 = i + (sum / 2)。如果它是 < size 然后添加 arr[temp_2] 来计数。
设置 arr_2[i] = 计数。
在 for 循环结束时,我们将 arr_2[] 作为 sum 数组。
使用 for 循环打印总和数组 arr_2[]。
#include <bits/stdc++.h> using namespace std; void sum_array(int arr[], int size, int sum){ int count = 0; int arr_2[size]; int temp = sum / 2 + 1; for (int i = 0; i < temp; i++){ count = count + arr[i]; } arr_2[0] = count; for (int i = 1; i < size; i++){ int temp_1 = i − (sum / 2) − 1; if (temp_1 >= 0){ count = count − arr[temp_1]; } int temp_2 = i + (sum / 2); if (temp_2 < size){ count = count + arr[temp_2]; } arr_2[i] = count; } cout<<"Construction of sum−array with sum of elements in given range are: "; for (int i = 0; i < size; i++){ cout<< arr_2[i] << " "; } } int main(){ int arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 }; int sum = 3; int size = sizeof(arr) / sizeof(int); sum_array(arr, size, sum); return 0; }输出结果
如果我们运行上面的代码,它将生成以下输出 -
Construction of sum-array with sum of elements in given range are − 5 12 13 14 16 17 17 9 3