Leetcode-3427变长子数组求和
目录
Leetcode-3427变长子数组求和
Leetcode-3427变长子数组求和解法
依旧前缀和，
是一个套路，数组有len个元素，设置一个len+1个元素的数组cnt，cnt[0] = 0,cnt[i+1] = cnt[i]+nums[i]，避开了left为0时需要讨论的情况。left = x, right = y,最后结果 = cnt[y+1] - left[x],可以画个图理解下更直观。
C++代码
class Solution {
public:
int subarraySum(vector<int>& nums) {
int len =nums.size();
vector<int> cnt;
cnt.resize(len+1);
int ans = 0;
for(int i = 0; i <len ;i++){
cnt[i+1] = cnt[i]+nums[i];
}
for(int i = 0; i<len;i++){
ans+=cnt[i+1]-cnt[max(0,i-nums[i])];
}
return ans;
}
};