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)