前缀和

212. 单词搜索 II 问题重述 给定一个 m x n 二维字符网格 board 和一个由字符串组成的列表 words。请你找出所有可以由网格中的字母构成的单词，并以列表形式返回。 规则和 "单词搜索 I" 完全相同： 单词必须按照字母顺序，通过相邻的单元格内的字母构成。 “相邻”指水平或垂直相邻。 同一个单元格内的字母在同一个单词中不能被重复使用。 示例: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],...

二维前缀和 1. 问题场景：从一维到二维 我们先回忆一下一维前缀和。给你一个数组 arr，如果频繁地问你 arr[L...R] 的和，我们会预处理一个前缀和数组 preSum，其中 preSum[i] = arr[0] + ... + arr[i]。这样 sum(L, R) 就可以用 preSum[R] - preSum[L-1] 在 O(1) 时间内得到。 现在，我们把问题升级到二维： 给你一个二维矩阵 matrix，现在会非常频繁地问你：以 (r1, c1) 为左上角，以 (r2, c2)...

一维前缀和 1. 问题场景：为什么要用前缀和？ 我们从一个最简单的需求开始。想象一下，我给你一个数组 nums，然后我会反复地问你同一个问题：“请告诉我，nums 数组从下标 L 到 R 的所有元素的和是多少？” 暴力解法： 这个需求太简单了。你可能会想，这不就是写个 for 循环嘛！来一个查询 (L, R)，我就从 L 遍历到 R，把所有 nums[i] 加起来。 // 暴力解法 int sum = 0; for (int i = L; i <= R; i++) { sum += n...