[Leetcode] 2090. K Radius Subarray Averages

1. 문제링크

https://leetcode.com/problems/k-radius-subarray-averages

K Radius Subarray Averages - LeetCode

 

 

2. 키 포인트

현재 인덱스까지 더한값을 저장하는 배열을 만들고 업데이트한다 

nums = [1,2,3,4]라면

sums = [1,3,6,10]가 된다.

vector의 자료형을 int로 하면 overflow가 발생하므로  64-bit integer type으로 한다.

 

k는 radius(반지름)인데 현재 인덱스를 기준으로 양 옆이 idx-k < 0 이거나 idx+k >= nums.size()가 되는 경우는 값이 -1가 되고그렇지 않은 경우에는 현재 인덱스 값을 idx +- k의 합의 평균으로 업데이트한다.

 

 

 

3. solution

class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size(), maxLen = k * 2 + 1;        
        vector<int> v(n, -1);        
        vector<long long> presum(n, 0);
        presum[0] = nums[0];
        for(int i = 1; i < n; i++){
            presum[i] = nums[i] + presum[i-1];
        }       
        for(int i = k; i < n-k; i++){                        
            long long sum = presum[i+k];
            if(i+k+1 > maxLen)
                sum -= presum[i-k-1];
            v[i] = sum / maxLen;            
        }

        return v;
    }
};