DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Sum of variable length subarray

Problem

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];
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)