力扣：常用数据结构（一）：前缀和

来源：

灵神题单

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

简单前缀和，前n项和对应s[n+1]

class NumArray {     vector<int> s; public:     NumArray(vector<int>& nums) {         s.resize(nums.size()+1);         for(int i=0;i<nums.size();i++)            s[i+1]=s[i]+nums[i];     }          int sumRange(int left, int right) {         return s[right+1]-s[left];     } };  /**  * Your NumArray object will be instantiated and called as such:  * NumArray* obj = new NumArray(nums);  * int param_1 = obj->sumRange(left,right);  */

2559. 统计范围内的元音字符串数

class Solution { public:     vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {         vector<int> ant(queries.size()),s(words.size()+1);         s[0]=0;  string biao="aeiou";         for(int i=0;i!=words.size();i++)         {             int a=0;             char star=words[i].front(),fin=words[i].back();             if(biao.find(star)!=-1 and biao.find(fin)!=-1)                 a=1;             s[i+1]=s[i]+a;         }         for(int i=0;i!=queries.size();i++)         {             int st=queries[i][1]+1,et=queries[i][0];           ant[i]=s[st]-s[et];         }         return ant;     } };

53. 最大子数组和

class Solution { public:     int maxSubArray(vector<int>& nums) {        int mmax=-10005,mmin=0;        vector<int> s(nums.size()+1);        for(int i=0;i<nums.size();i++)        {             s[i+1]=s[i]+nums[i];             mmax=max(mmax,s[i+1]-mmin);             mmin=min(mmin,s[i+1]);        }        return mmax;      } };