TC: O(n)
SC:O(n)
class Solution {
public int subarraySum(int[] nums) {
int prefix[] = new int[nums.length];
prefix[0] = nums[0];
for(int i =1;i<nums.length;i++){
prefix[i] = prefix[i-1]+nums[i];
}
int sum =0;
for(int i =0;i< nums.length;i++){
int start = Math.max(0,i-nums[i]);
int end = i;
sum+=get(start,end,prefix);
}
return sum;
}
public int get(int i, int j, int prefix[]){
if(i<1) return prefix[j];
return prefix[j]-prefix[i-1];
}
}
Top comments (0)