算法 |
您所在的位置：网站首页 › 什么是邮箱前缀和后缀 › 算法 |
算法
|
1. 什么是前缀和算法
前缀和算法（Prefix Sum）是一种用于快速计算数组元素之和的技术。它通过预先计算数组中每个位置前所有元素的累加和，将这些部分和存储在一个新的数组中，从而在需要计算某个区间的和时，可以通过简单的减法操作得到结果，而不必重新遍历整个区间。 2. 一维前缀和在这里我们通过一个例题来讲解：【模板】前缀和_牛客题霸_牛客网 (nowcoder.com) 题目描述如下
我们在一个数组中想要q次访问一段下标为 [l, r] 的数据和即
我们稍加分析可以发现，如果我们使用暴力解法（将区间内所有数字相加）时间复杂度为O(q*N)，在这里我们可以使用前缀和的算法，来使每次访问的时间复杂度降低到O(1)，在这里我们要提前预备好一个dp数组，dp[i]表示从下标1开始到下标i的数值和，dp[i] = dp[i-1] + arr[i]，这样填完dp表后，[l, r]的数值和sum = dp[r] - dp[l-1]，此外在这里有一个细节需要我们注意：下标为什么是从1开始的？——假如要计算[0, 2]的话，我们需要使用dp[2] - dp[-1]，这样就会带来不便。 我们可以得到这道题的代码 #include #include using namespace std; int main() { int n = 0, q = 0; cin >> n >> q; vector arr(n + 1); for (int i = 1; i > arr[i]; // 使用long long 避免整型溢出 vector dp(n + 1); for (int i = 1; i > l >> r; cout (i, j)所有数值和，我们要计算的dp[i][j]可以按如下方式计算
即dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]，在预备好了dp数组过后，我们如何来使用它呢？图解如下
我们可以使用如下代码解决此问题 #include #include using namespace std; int main() { int n = 0, m = 0, q = 0; cin >> n >> m >> q; vector arr(n + 1, vector(m + 1)); for (int i = 1; i arr[i][j]; vector dp(n + 1, vector(m + 1)); for (int i = 1; i x1 >> y1 >> x2 >> y2; cout sum%k==x%k这样一个区间，即
此外，我们还需要注意一个细节就是一个负数%正数的时候，其结果会是负数，我们可以使用(sum%k + k)来修正这个负数，但是当sum为正时，我们会多加一个k此时再%k即可解决，因此我们的修正公式为(sum%k + k)%k，细节问题与上面的第3题类似，这里就不过多赘述，代码如下 class Solution { public: int subarraysDivByK(vector& nums, int k) { int ret = 0; unordered_map hash; hash[0] = 1; int sum = 0; for (auto e : nums) { sum += e; int mod = (sum % k + k) % k; if (hash.count(mod)) ret += hash[mod]; hash[mod]++; } return ret; } }; 5. 连续数组题目链接：525. 连续数组 - 力扣（LeetCode）
解析：对于这道题我们直接解决还是有点困难，可以先将0转换成-1，这样就与我们之前做的和为k的子数组相似了，我们还是可以定义dp[i]是以i位置为结尾的所有子数组，要想找到和为0的子数组只需要找到sum相同的区间，并计算这个区间的长度，图示如下
我们要想知道区间长度，就需要知道i和j，因此我们向哈希表中存入的value为当前前缀和的下标。此外，如果我们再次遇到一个值为sum的下标，由于这里求得是最长区间，所以我们不需要更新hash[sum]。而如果整个区间的长度都为0，那么我们就需要在前缀和为0的情况下，找到一个下标为-1的地方来统计整个数组长度。此外，我们计算长度时，图解如下
我们可以得到代码如下 class Solution { public: int findMaxLength(vector& nums) { for (auto& e : nums) if (e == 0) e = -1; unordered_map hash; hash[0] = -1; int ret = 0; int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; if (hash.count(sum)) ret = max(ret, i - hash[sum]); else hash[sum] = i; } return ret; } }; 6. 矩阵区域和题目链接：1314. 矩阵区域和 - 力扣（LeetCode）
解析： 在之前我们已经推导过二维前缀和的初始化与使用，在这里我们需要关注的是下标在dp数组与mat数组之间的映射关系，为了便于初始化我们将dp设置成一个大小为(n+1)*(m+1)的数组，因此dp[i][j]就对应着mat[i-1][j-1]。分析一下题意我们可以知道，这道题的意思是ret[i][j]表示从(i-k, j-k)->(i+k, j+k)的所有数值之和，且下标均要合法，我们可以使用min与max函数来分别控制下标有效，那么我们可以得到如下代码 class Solution { public: vector matrixBlockSum(vector& mat, int k) { int m = mat.size(), n = mat[0].size(); vector dp(m + 1, vector(n + 1)); for (int i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |