阅读量:0
来源：
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; } };