Problem Statement

You are given an array of integers nums and an integer k. Your task is to find the sum of every contiguous subarray of size k within the array and return the result as a vector.

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5], K = 3

Output: [6, 9, 12]

Explanation:

* Window [1, 2, 3] = Sum 1+2+3 = 6
* Window [2, 3, 4] = Sum 2+3+4 = 9
* Window [3, 4, 5] = Sum 3+4+5 = 12

Example 2:

Input: nums = [3, 4, 5, 1, 2, 6], K = 2

Output: [7, 9, 6, 3, 8]

Explanation:

Subarrays of size 2 are [3, 4], [4, 5], [5, 1], [1, 2], and [2, 6]. Their sums are 7, 9, 6, 3, and 8, respectively.

Different Approaches

1 Brute Force Approach

In the brute force approach, we calculate the sum of every contiguous subarray of size k within the given array. For each index i from 0 to n - k, we calculate the sum of the next k elements starting from index i.

Algorithm:

1. Initialize an empty vector result to store the sum of all subarrays.
2. Iterate through the array nums from index 0 to n - k.
   1. For each index i, calculate the sum of the next k elements starting from index i.
   2. Append the sum to the result vector.
3. Return the result vector.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

vector<int> sumOfSubarrays(vector<int>& nums, int k) {
    vector<int> result;
    int n = nums.size();
    
    // Iterate through the array from index 0 to n - k
    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        
        // Calculate the sum of the next k elements starting from index i
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        
        // Append the sum to the result vector
        result.push_back(sum);
    }
    
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int k = 3;
    vector<int> result = sumOfSubarrays(nums, k);
    
    // Print the sum of all subarrays of size k
    cout << "Sum of all subarrays of size " << k << ":" << endl;
    for (int sum : result) {
        cout << sum << " ";
    }
    cout << endl;
    
    return 0;
}

Explanation:

• In the sumOfSubarrays function, we iterate through the array nums from index 0 to n - k.
• For each index i, we calculate the sum of the next k elements starting from index i.
• We append each sum to the result vector.
• Finally, we return the result vector containing the sum of all subarrays of size k.

Complexity Analysis:

Time Complexity:O(n*k)

• where n is the size of the input array nums and k is the size of the subarray.

Space Complexity:O(k)

• where k is the size of the subarray (window).

2 Sliding Window Approach

The sliding window technique is used to solve this problem efficiently. We can calculate the sum of the first k elements and then slide the window by moving the right pointer to the right and the left pointer to the right.

Algorithm:

1. Initialize two pointers left and right to 0.
2. Initialize a variable sum to 0 to store the sum of elements in the current window.
3. Slide the window:
   1. Add the element at the right pointer to sum.
   2. If the window size exceeds K, subtract the element going out of the window from sum and move the left pointer to the right.
   3. If the window size is equal to K, add sum to the result vector.
   4. Move the right pointer to the right to expand the window.
4. Repeat step 3 until the right pointer reaches the end of the array.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

vector<int> sumOfSubarrays(vector<int>& nums, int k) {
    vector<int> result;
    int n = nums.size();
    int left = 0, right = 0;
    int sum = 0;
    
    // Slide the window and calculate the sum of each subarray
    while (right < n) {
        sum += nums[right]; // Add the element at the right pointer to sum
        
        // If the window size exceeds k, move the left pointer to slide the window
        if (right - left + 1 > k) {
            sum -= nums[left]; // Subtract the element going out of the window
            left++; // Move the left pointer
        }
        
        // If the window size is equal to k, add the sum to the result vector
        if (right - left + 1 == k) {
            result.push_back(sum);
        }
        
        right++; // Move the right pointer to expand the window
    }
    
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int k = 3;
    vector<int> result = sumOfSubarrays(nums, k);
    
    cout << "Sum of all subarrays of size " << k << ":" << endl;
    for (int sum : result) {
        cout << sum << " ";
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

• Where n is the size of the input array nums.
• We iterate through the array only once.

Space Complexity:O(1)