สร้าง Sum-Array จากผลรวมในช่วงกำหนด (Sliding Window) ใน C++

โจทย์: ให้อาร์เรย์ arr[] และเลขคี่ sum ต้องการสร้าง sum-array arr2[] โดยที่ arr2[i] = ผลรวมของ arr[i-sum/2] ถึง arr[i+sum/2] (ปรับขอบเขตที่ขอบอาร์เรย์)

แนวคิด: Sliding Window

ใช้หน้าต่างขนาด sum เลื่อนไปเรื่อยๆ โดยลบองค์ประกอบซ้ายสุดและบวกองค์ประกอบขวาสุด

อัลกอริทึม

1. คำนวณผลรวมเริ่มต้นของหน้าต่างแรก (size = sum/2 + 1)
2. สำหรับ i = 1 ถึง n-1:
   • ลบ arr[i - sum/2 - 1] ถ้าอยู่ในขอบเขต
   • บวก arr[i + sum/2] ถ้าอยู่ในขอบเขต
   • arr2[i] = ผลรวมปัจจุบัน

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

void sum_array(int arr[], int size, int sum) {
    int count = 0;
    int arr2[size];
    int half = sum / 2;
    int window_size = half + 1;
    
    // หน้าต่างแรก
    for (int i = 0; i < window_size && i < size; i++)
        count += arr[i];
    arr2[0] = count;
    
    // เลื่อนหน้าต่าง
    for (int i = 1; i < size; i++) {
        int left_out = i - half - 1;
        if (left_out >= 0) count -= arr[left_out];
        
        int right_in = i + half;
        if (right_in < size) count += arr[right_in];
        
        arr2[i] = count;
    }
    
    cout << "Sum-array: ";
    for (int i = 0; i < size; i++)
        cout << arr2[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

การคำนวณตัวอย่าง (sum=3, half=1)

ความซับซ้อน: Time O(n), Space O(n)