前缀和：数组nums[]的第0项到当前项的和，用数组prefixSum表示的话，x为当前项，则有：
prefixSum[x]=nums[0]+nums[1]+…+nums[x]
从前缀和可以推出：
nums 的某项 = 两个相邻前缀和的差：
nums[x] = prefixSum[x] - prefixSum[x - 1]

nums 的 第 i 到 j 项 的和，有：
nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]

当 i 为 0，此时 i-1 为 -1，我们故意让 prefixSum[-1] 为 0，使得通式在i=0时也成立：
nums[0] +…+nums[j]=prefixSum[j]

一、和为K的子数组，LC560

image.png

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int size = nums.length;
  4.         //前缀和
  5.         int[] prefixSum = new int[size+1];
  6.         prefixSum[0] = 0;
  7.         prefixSum[1] = nums[0];
  8.         for (int i=1; i<size; i++) {
  9.             prefixSum[i+1] = nums[i] + prefixSum[i];
  10.         }
  12.         int cnt = 0;
  13.         for (int i=0; i<=size; i++) {
  14.             for (int j=i+1; j<=size; j++) {
  15.                 if (prefixSum[j] - prefixSum[i] == k) {
  16.                     cnt++;
  17.                 }
  18.             }
  19.         }
  20.         return cnt;
  22.     }
  23. }
  24. class Solution {
  25.     public int subarraySum(int[] nums, int k) {
  26.         //前缀和+HashMap
  27.         //记录前缀和-k出现的次数就行
  28.         Map<Integer, Integer> map = new HashMap<>();
  29.         //自身也可以满足
  30.         map.put(0, 1);
  31.         int size = nums.length;
  32.         int prefixNum = 0;
  33.         int cnt = 0;
  34.         for (int i=0; i<size; i++) {
  35.             prefixNum += nums[i];
  36.             if (map.containsKey(prefixNum - k)) {
  37.                 cnt += map.get(prefixNum-k);
  38.             }
  39.             map.put(prefixNum, map.getOrDefault(prefixNum, 0)+1); //记录每个前缀和
  40.         }
  41.         return cnt;
  42.     }
  43. }

二、统计【优美子数组】

image.png

三、连续数组，LC525

image.png

  1. class Solution {
  2.     public int findMaxLength(int[] nums) {
  3.         int size = nums.length;
  4.         int res = 0;
  5.         //前缀和 下标
  6.         Map<Integer, Integer> map = new HashMap<>();
  7.         map.put(0, -1);
  8.         int preSum = 0;
  9.         for (int i=0; i<size; i++) {
  10.             if (nums[i] == 1) {
  11.                 preSum++;
  12.             } else {
  13.                 preSum--;
  14.             }
  15.             if (map.containsKey(preSum)) {
  16.                 int index = map.get(preSum);
  17.                 res = Math.max(res, i - index);
  18.             } else {
  19.                 map.put(preSum, i);
  20.             }
  21.         }
  22.         return res;
  23.     }
  25.     //超时
  26.     // public int findMaxLength(int[] nums) {
  27.     //     int size = nums.length;
  28.     //     //前缀和
  29.     //     int[] preSum = new int[size+1];
  30.     //     preSum[0] = 0;
  31.     //     for (int i=0; i<size; i++) {
  32.     //         if (nums[i] == 0) {
  33.     //             nums[i] = -1;
  34.     //         }
  35.     //         preSum[i+1] = nums[i] + preSum[i];
  36.     //     }
  38.     //     int res = 0;
  39.     //     for (int i=0; i<=size; i++) {
  40.     //         for (int j=i; j<=size; j++) {
  41.     //             if (preSum[i] - preSum[j] == 0) {
  42.     //                 res = Math.max(res, j-i);
  43.     //             }
  44.     //         }
  45.     //     }
  46.     //     return res;
  47.     // }
  48. }