source

定义子数组之和:
let sum(i,j) = nums[i]+nums[i+1]...+nums[j]

前缀和 preSum

For given integer array nums of length n, we create a preSum array preSum of length n+1, with following features:

• preSum[i] = sum(0,i-1), i.e. sum of first i entries of nums
• sum(i,j) = preSum[j+1]-preSum[i]

代码

int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
    preSum[i + 1] = preSum[i] + nums[i];