:::success

经典参考：
秒杀七道题
吴师兄-LeetCode 例题精讲 | 18 前缀和：空间换时间的技巧
前缀和 & 差分
前缀和&&差分-知乎

TODO：

什么是前缀和？

应用：

  • 求子数组
  • 求子串

    分析&模板

    pre[i] = pre[i -1] + nums[i]

1310. 子数组异或查询

前缀异或
pre[i + 1] = pre[i] + nums[i]
case 1: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] => [2,7,14,8]
xors [ 0, 1, 2, 6, 14 ]

case 2: [15,8,8,8,15] [[2,2],[3,3]] [8,8]

  1. var xorQueries = function(arr, queries) {
  2.     let n = arr.length;
  3.     let pre = new Array(n + 1).fill(0);
  4.     for (let i = 0; i < n; i++) {
  5.         pre[i + 1] = pre[i] ^ arr[i]; 
  6.     }
  7.     let res = [];
  8.     for (let query of queries) {
  9.         let [start, end] = query;
  10.         res.push(pre[start] ^ pre[end + 1]);
  11.     }
  12.     return res;
  13. };

1915. 最美子字符串的数目

状态压缩+前缀和

  1. var wonderfulSubstrings = function(word) {
  2.     let n = 1 << 10;
  3.     let counts = new Array(n).fill(0);
  4.     counts[0] = 1;
  5.     let pre = 0;
  6.     let ans = 0;
  7.     for (let c of word) {
  8.         let cur = c.charCodeAt(0) - 'a'.charCodeAt(0);
  9.         pre ^= (1 << cur);
  10.         ans += counts[pre];
  11.         for (let i = 1; i < n; i <<= 1) {
  12.             ans += counts[pre ^ i];
  13.         }
  14.         ++counts[pre];
  15.     }
  16.     return ans;
  17. };

参考