303.区域和检索-数组不可变

class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        // 获取前缀和
        sums.resize(n+1);
        for (int i = 0; i < n; i++) {
            sums[i+1] = sums[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
    	// 根据前缀和O(1)拿到[i,j]的和
        return sums[j+1] - sums[i];
    }
};

1480.一维数组的动态和

class Solution {
public:
	// 求前缀和
    vector<int> runningSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        result[0] = nums[0];
        for(int i{};i<n;++i){
            if(i) result[i] = result[i-1] + nums[i]; 
        }

        return result;
    }
};

1991.找到数组的中间位置

class Solution {
public:
	// 前缀和的应用
    int findMiddleIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n+1);

        int sumResult = accumulate(nums.begin(),nums.end(),0);

        for(int i{};i<n;++i) {
            sums[i+1] = sums[i] + nums[i];

            if(sums[i]*2 + nums[i] == sumResult) return i;
        }

        return -1;
    }
};

643.子数组最大平均数I

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> sums(n+1);
		// 使用前缀和将时间复杂度控制在O(n)
        for(int i{};i<n;++i) sums[i+1] = sums[i] + nums[i];

        double result{INT_MIN};
        for(int i{};i<n-k+1;i++){
            double average = (sums[i+k] - sums[i])/k;

            if(average > result) result = average;
        }

        return result;
    }
};

1413.逐步求和得到正数的最小值

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int n = nums.size();

        vector<int> sums(n+1);
		// 前缀和的应用
		// 找最小的前缀和
        int minResult{INT_MAX};
        for(int i{};i<n;++i){
            sums[i+1] = sums[i] + nums[i];
            if(sums[i+1] < minResult) minResult = sums[i+1];
        } 

        return minResult >=0 ? 1 : abs(minResult) + 1;
    }
};

1588.所有奇数长度子数组的和

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();

        vector<int> sums(n+1);
		// 通过前缀和，将时间复杂度控制在O(n^2)
        for(int i{};i<n;++i) sums[i+1] = sums[i] + arr[i];

        int result{};
        for(int i{};i<n;++i){
            for(int j{1};(i+j-1)<n;j+=2){
                result += (sums[i+j]-sums[i]);
            }
        }

        return result;
    }
};

1732.找到最高海拔

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int n = gain.size();
        vector<int> sums(n+1);

        int result{INT_MIN};
		// 前缀和求解
        for(int i{};i<n;++i){
            sums[i+1] = sums[i] + gain[i];
            if(result < sums[i]) result = sums[i];
        } 
        if(result < sums[n]) result = sums[n];
        return result;
    }
};