前缀和

560.和为K的子数组

算出一共有几个和为 k 的子数组。这里用到了前缀和数组。

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];

前缀和示意图（来自于labuladong）

注意以下几点：

• 前缀和数组第0号索引即preSum[0]代表了前0个数的前缀和

• preSum[3]代表了前三个数的前缀和，其中以末尾元素nums[3-1]为参考，意思是nums[0,1,2]三者之和，nums[2]是参考元素

• 若要求nums[ i~~j ]之和，只需要preSum[j+1]-preSum[i]即可，用具体的例子来看的话，假设i=1，j=3，那么中间这三个数等于前四个数减去前一个数，翻译过来就是preSum[3+1]-preSum[1]

  //时间复杂度：O(N^2)    空间复杂度：O(N)
  public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // 构造前缀和
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++)
            preSum[i + 1] = preSum[i] + nums[i];

        int ans = 0;
        for (int i = 1; i <= len; i++)
            for (int j = 0; j < i; j++)
                if (preSum[i] - preSum[j] == k)
                    ans++;
        return ans;
    }

Tips

• 前半部分为前缀和构造，不多言了
• 后半部分为穷举子数组，而且是穷举以nums[i-1]为结尾的子数组，从这个角度来说，i 的取值范围为[1,len]就无可厚非了，因为i-1的取值范围正好是[0,len-1]。假设preSum[i=3]，那么结尾元素为nums[2]，从3，5，2→5，2→2

优化

• 摈弃 preSum 数组，引入哈希表
• 我们不关心前缀和具体对应哪一项，只关心前缀和的值和出现次数。所以出现过的前缀和，和对应的出现次数，存入 map 即可
  map 存：
  键： 前缀和，从第 0 项到当前项的总和
  值： 这个前缀和值出现了几次
• 举个栗子~~~ 还是看前缀和示意图，假设k=7，这意味nums[1~~2]是一个解，那么从nums[0]开始，用一个变量不停地累加滚动前缀和的值(不用再开数组了)，检查当前前缀和减去k是不是我想要的答案（去哈希表里查），如果当前前缀和不在哈希表中，那就put进去，
  这么说可能绕进去了，直接看图，一开始preSum是3，3-7=-4，-4不在哈希表中，前缀和3存入哈希表，然后是5，preSum=3+5=8，8-7=1，1不在哈希表中，8存入哈希表，再然后是2，preSum=3+5+2=10，10-7 =3，3在哈希表中，更新ans。

我感觉这么说还是很复杂

for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
        if (preSum[i] - preSum[j] == k)
            ans++;

if (preSum[j] == preSum[i] - k)
    ans++;

重点还是在这里，在最初的代码中，我们是每次砍掉一个来判断子数组的和等不等于k,但现在呢，如下面的代码，我们做了等式变形，只关注有几个前缀和等于我想要的答案。本来我们是前缀和与前缀和做减法，希望得到想要的结果，但现在我们是直接前缀和与结果做减法，寻找我想要的前缀和，注意每个前缀和都是不重复的，虽然值有可能相同。

    //时间复杂度：O(N)    空间复杂度：O(N)
    //这样一来，通过哈希表记录每次的前缀和，时间复杂度也降为了线性
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        // preSum：前缀和 -> 该前缀和出现的次数
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        int sum0_i = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            sum0_i += nums[i];
            int sum0_j = sum0_i - k;
            if (preSum.containsKey(sum0_j))
                ans += preSum.get(sum0_j);
            preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0) + 1);
        }
        return ans;
    }