【前缀和】算法实战

文章目录

  • 一、算法原理
    • 1. 一维前缀和
    • 2. 二维前缀和
  • 二、算法实战
    • 1. leetcode560 和为K的子数组
    • 2. leetcode974 和可被K整除的子数组
    • 3. leetcode525 连续数组
    • 4. leetcode1314 矩阵区域和
    • 5. leetcode724 寻找数组的中心下标
    • 6. leetcode238 除自身以外数组的乘积
  • 三、总结

一、算法原理

前缀和算法指的是某段序列的前n项和，前缀和一般用来求数组中某段连续区间的和。下面我们来看一下它的算法原理。

1. 一维前缀和

在这里插入图片描述
前缀和

思路：

先预处理一个前缀和数组：dp[i] 表示 [1, i] 区间内所有元素的和。dp数组的递推公式为：dp[i] = dp[i - 1] + arr[i];这里我们的数组下标从1开始是为了处理边界情况。

使用前缀和数组：[ l , r ]区间和 = dp[ r ] - dp[ l - 1 ];

代码实现：

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 101010;
int arr[N];
LL dp[N];

int main() 
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    
    for(int i = 1; i <= n; i++)
        dp[i] = dp[i - 1] + arr[i];
    while(m--)
    {
        int l, r;
        cin >> l >> r;
        printf("%lld\n", dp[r] - dp[l - 1]);
    }
    return 0;
}

2. 二维前缀和

在这里插入图片描述
二维前缀和

思路：

类⽐于⼀维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这⽚区域内所有元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们接下来仅需完成两步即可：

  • 第⼀步：搞出来前缀和矩阵
    这⾥就要⽤到⼀维数组⾥⾯的拓展知识，我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列，这样我们就可以省去⾮常多的边界条件的处理（同学们可以⾃⾏尝试直接搞出来前缀和矩阵，边界条件的处理会让你崩溃的）。处理后的矩阵就像这样：
    在这里插入图片描述
    这样，我们填写前缀和矩阵数组的时候，下标直接从 1 开始，能⼤胆使⽤【i - 1 , j - 1】 位置的值。
  • 递推方程
    递推⽅程就是：sum[i][j]=sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]+matrix[i - 1][j - 1]
  • 使用前缀和矩阵：
    在这里插入图片描述
    目标矩阵的面积 = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

代码实现：

#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;

int n, m, q;

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    vector<vector<long long>> dp(n+1,vector<long long>(m+1, 0));
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%lld", &dp[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%lld\n", dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
    }

    return 0;
}

二、算法实战

1. leetcode560 和为K的子数组

在这里插入图片描述
和为K的子数组

解题思路：前缀和 + 哈希表

在这里插入图片描述

我们可以将这个问题的求解转换一下，这道题的原意是让我们求以i为结尾的所有满足要求的子数组，我们可以将问题转换为：在[0, i - 1]区间内，有多少前缀和等于sum[i] - k。

我们建立哈希表，以和为键，出现的次数为对应的值，记录prev[i]出现的次数，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1) 时间内得到。由于prev[i]的计算只与前一项的答案有关，因此我们直接用prev变量来记录答案即可。

这里有一个细节问题，如果整个前缀和等于K需要特殊处理一下，我们需要提前让hash表中的hash[0] = 1;

代码实现：

// 写法一:
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int pre = 0, cnt = 0;
        hash[0] = 1;
        for(auto& e : nums)
        {
            pre += e;
            if(hash.find(pre - k) != hash.end())
                cnt += hash[pre - k];
            hash[pre]++;
        }
        return cnt;
    }
};
// 写法二:
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] + nums[i - 1];
        unordered_map<int,int> hash;
        int res = 0;
        hash.insert({0, 1});
        for(int i = 1; i <= n; i++)
        {
            res += hash[pre[i] - k];
            hash[pre[i]]++;
        }
        return res;
    }
};

2. leetcode974 和可被K整除的子数组

在这里插入图片描述
和可被K整除的子数组

补充知识：同余定理+(C++、Java)中[负数%正数]的结果以及修正

在这里插入图片描述

解题思路：前缀和+哈希表

这道题和上一道题目很相似。一个是求和为k的子数组，一个是求和可被k整除的子数组，方法是一样的。首先使用pre变量来遍历数组存储到目前为止的前缀和，根据同余定理，只需要满足pre[j] mod K == pre[i-1] mod K即可。

我们可以考虑对数组进行遍历，在遍历同时统计答案。当我们遍历到第 i 个元素时，我们统计以 ji 结尾的符合条件的子数组个数。然后维护一个以前缀和模 K 的值为键，出现次数为值的哈希表 ，在遍历的同时进行更新。这样类似上一题进行维护和计算即可得到结果。

代码实现：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int pre = 0, cnt = 0;
        hash[0] = 1;
        for(auto& e : nums)
        {
            pre += e;
            int r = ((pre - k) % k + k) % k;
            if(hash.find(r) != hash.end())
                cnt += hash[r];
            hash[r]++;
        }
        return cnt;
    }
};

3. leetcode525 连续数组

在这里插入图片描述
连续数组

解题思路：前缀和+哈希表

根据题意可得，数组中的元素不是0就是1，题目要求我们找到含有相同数量的 0 和 1 的最长连续子数组，那么我们可以转化一下思路：1. 将所有的0修改为-1。2. 在数组中找出最长的子数组，使数组中所有元素的和为0。

这里我们还是使用前缀和+哈希表的方式来解决。在哈希表中存的是前缀和的末尾元素的下标。当哈希表中有重复的<sum,i>时，只保留前面那一对<sum,i>，当判断某一对前缀和在哈希表中出现过时，说明【后者-前者】区间内的元素之和为0。这时，我们使用一个Max变量来更新我们的结果即可。当然，区间长度=[当前下标-前一个前缀和等于0的末尾元素下标]，否者则将该前缀和的末尾元素下标丢入哈希表即可。这保证了我们如果有重复的<sum,i>，只存储前面那一对<sum,i>。当然别忘了，如果遇到数组中所有元素之和等于0，这种情况我们需要特殊处理一下，就是将hash[0]=-1。

代码实现：

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        int pre = 0, Max = 0;
        
        hash[0] = -1;
        for(int i = 0; i < nums.size(); i++)
        {
            if(!nums[i]) nums[i] = -1;
            pre += nums[i];
            if(hash.count(pre))
                Max = max(Max, i - hash[pre]);
            else
                hash[pre] = i;
        }
        return Max;
    }
};

4. leetcode1314 矩阵区域和

在这里插入图片描述
矩阵区域和

解题思路：二维前缀和

首先我们需要读懂题目的含义，我们需要将原数组的每个元素变成对应矩阵范围的区域和，为了能够快速求出矩阵某段区域的面积之和。因此我们需要构造前缀和数组。

因为我们所学习的前缀和数组下表是从1开始的，但是在力扣中的数组的下标都是从0开始的，所以我们构造前缀和数组时需要将前缀和数组在原数组的基础上添加一行一列，以便于后续好处理。

但是这道题目真正的难点在于下标之间的关系，因为前缀和数组的下标是从1开始的，但是我们所求的目标数组又是从0开始的，所以这之间就必须要存在一种转换关系，需要我们自己把握。

代码实现：

class Solution {
public:
    int getRet(int x1, int x2, int y1, int y2)
    {
        return tmp[x2][y2] - tmp[x1 - 1][y2] - tmp[x2][y1 - 1] + tmp[x1 - 1][y1 - 1];
    }
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        tmp = vector<vector<int>>(n + 1, vector<int>(m + 1));

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1] - tmp[i - 1][j - 1] + mat[i - 1][j - 1];
        
        // 目标数组
        vector<vector<int>> ret(n, vector<int>(m));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                int x1 = max(i - k, 1);
                int x2 = min(i + k, n);
                int y1 = max(j - k, 1);
                int y2 = min(j + k, m);
                ret[i - 1][j - 1] = getRet(x1, x2, y1, y2);
            }
        return ret;
    }
private:
    vector<vector<int>> tmp; // 前缀和数组
};

5. leetcode724 寻找数组的中心下标

在这里插入图片描述
寻找数组的中心下标

解题思路：

题目要求我们求解数组的中心下标，中心下标的定义为：其左侧所有元素相加的和等于右侧所有元素相加的和。根据题目的这个意思，我们可以构建前缀和数组。我们可以根据：左侧元素相加之和=dp[n - 1] - dp[i]，右侧元素相加之和=dp[i-1]，我们使用左侧元素减去右侧元素之和，看结果是否为0，如果为零，该位置则为数组的中心下标。当然我们需要注意边界情况特殊处理一下即可。

代码实现：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int ret = -1, n = nums.size();
        int dp[10001] = {0};
        for(int i = 0; i < n; i++){
            if(i == 0) dp[0] = nums[0];
            else dp[i] = dp[i - 1] + nums[i];
        }
        
        for(int i = 0; i < n; i++)
        {
            int tmp = 0;
            if(i == 0)
                tmp = dp[n - 1] - nums[i];
            else if(i == n - 1)
                tmp = dp[n - 1] - nums[n - 1];
            else
                tmp = dp[n - 1] - dp[i] - dp[i - 1];
            
            if(tmp == 0)
                return i;
        }
        return ret;

    }
};

6. leetcode238 除自身以外数组的乘积

在这里插入图片描述
除自身以外数组的乘积

解题思路：

这道题的要求是让我们将数组中的每个元素变成除了它自身外其他元素之积，我们可以根据前缀和的思想，构造两个数组：前缀积数组和后缀积数组。前缀积数组： f[i]表示 [0, i-1] 区间内所有元素的乘积。后缀积数组： g[i]表示 [i+1, n-1] 区间内所有元素的乘积。我们求目标数组的元素时直接 ret[i] = f[i] * g[i] 即可。

当然这道题目我们还可以使用滚动数组进行优化，原本需要开三个数组，但是优化后只需要一个数组就可以解决。先开一个前缀积数组，然后求出前缀积。然后接下来for循环从后往前遍历，因为后缀积数组的后一项可以推出前一项，所以使用一个临时变量right来依次滚动推导每一次需要使用的后缀积，然后乘以前缀积数组中的元素，就可以直接将前缀积数组推导成为目标数组。

代码实现：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return {};
        vector<int> ret(n, 0);
        ret[0] = 1;
        for(int i = 1; i < n; i++)
        {
            ret[i] = ret[i - 1]*nums[i - 1];
        }
        int right = 1;
        for(int i = n - 1; i >= 0; i--)
        {
            ret[i] *= right;
            right *= nums[i];
        }
        return ret;
    }
};

三、总结

在算法题中，前缀和计算时间复杂度为O(n)，后续要查询对应的操作算法复杂度为O(1)，使用前缀和后，能大大减少算法复杂度。同时，前缀和属于「空间换时间」的算法或者也可以说不是算法，而是一种数组的「预处理」。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/82578.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux/Ubuntu 的日常升级和安全更新，如何操作？

Linux/Ubuntu 的日常升级和安全更新，如何操作？

我安装的是Ubuntu 20.04.6 LTS的Windows上Linux子系统版本&#xff0c;启动完成后显示&#xff1a; Welcome to Ubuntu 20.04.6 LTS (GNU/Linux 5.15.90.4-microsoft-standard-WSL2 x86_64) * Documentation: https://help.ubuntu.com * Management: https://landscape.c…
阅读更多...
每天一道leetcode：934. 最短的桥（图论中等广度优先遍历）

每天一道leetcode：934. 最短的桥（图论中等广度优先遍历）

今日份题目&#xff1a; 给你一个大小为 n x n 的二元矩阵 grid &#xff0c;其中 1 表示陆地&#xff0c;0 表示水域。 岛 是由四面相连的 1 形成的一个最大组&#xff0c;即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 &#…
阅读更多...
Go 安装配置

Go 安装配置

介绍Ubuntu20.04 安装和配置Go 可以参考官网的这个为 Go 开发配置Visual Studio Code - Go on Azure | Microsoft Learn 1.安装Go 去这个地方下载Go https://go.dev/doc/install 如果之前安装过&#xff0c;可以参考这个&#xff08;没有可以忽略&#xff09; 下载完成后执…
阅读更多...
Linux Shell如果ping失败就重启网卡（详解）

Linux Shell如果ping失败就重启网卡（详解）

直接上脚本 -------------------------------------------------------------------------- #vi /tmp/ping_check.sh #!/bin/bash IP="1.1.1.1" PacketLoss=`ping -c 4 -w 4 1.1.1.1 | grep packet loss | awk -F packet loss {print $1} | awk {print $NF}|se…
阅读更多...
vsCode使用cuda

vsCode使用cuda

一、vsCode使用cuda 前情提要&#xff1a;配置好mingw&#xff1a; 1.安装cuda 参考&#xff1a; **CUDA Toolkit安装教程&#xff08;Windows&#xff09;&#xff1a;**https://blog.csdn.net/qq_42951560/article/details/116131410 2.在vscode中添加includePath c_cp…
阅读更多...
Midjourney API 申请及使用

Midjourney API 申请及使用

在人工智能绘图领域&#xff0c;想必大家听说过 Midjourney 的大名吧&#xff01; Midjourney 以其出色的绘图能力在业界独树一帜。无需过多复杂的操作&#xff0c;只要简单输入绘图指令&#xff0c;这个神奇的工具就能在瞬间为我们呈现出对应的图像。无论是任何物体还是任何风…
阅读更多...
Android内存泄漏总结和性能优化技巧

Android内存泄漏总结和性能优化技巧

我们在开发安卓应用时&#xff0c;性能优化是非常重要的方面。一方面&#xff0c;优化可以提高应用的响应速度、降低卡顿率和提升应用流畅度&#xff0c;从而提升用户体验&#xff1b;另一方面&#xff0c;优化也可以减少应用的资源占用&#xff0c;提高应用的稳定性和安全性&a…
阅读更多...
如何在window下cmd窗口执行linux指令？

如何在window下cmd窗口执行linux指令？

1.Git&#xff1a;https://git-scm.com/downloads(官网地址) 2.根据自己的实际路径,添加两个环境变量 3.重启电脑
阅读更多...
【Selenium学习】环境搭建 API学习

【Selenium学习】环境搭建 API学习

目录 一、javaSelenium的环境搭建&#xff1f; 二、认识Selenium 1、什么是自动化&#xff1f; 2、什么是Selenium? (重点) 3、selenium的工作原理&#xff1f;&#xff08;重点&#xff09; 三、Selenium操作元素API&#xff08;重点&#xff09; 第一部分&#…
阅读更多...
使用 HTML、CSS 和 JavaScript 创建实时 Web 编辑器

使用 HTML、CSS 和 JavaScript 创建实时 Web 编辑器

使用 HTML、CSS 和 JavaScript 创建实时 Web 编辑器 在本文中&#xff0c;我们将创建一个实时网页编辑器。这是一个 Web 应用程序&#xff0c;允许我们在网页上编写 HTML、CSS 和 JavaScript 代码并实时查看结果。这是学习 Web 开发和测试代码片段的绝佳工具。我们将使用ifram…
阅读更多...
excel中有哪些通配符、excel配置问题，数学函数篇1之sum系列

excel中有哪些通配符、excel配置问题，数学函数篇1之sum系列

学习excel前需要明确的是事&#xff1a;   在学习excel函数之前&#xff0c;大家需要明确一件事&#xff0c;excel现在设计到了一些新函数&#xff0c;这些新函数只能存在于office365、office2019及更 新版本之中&#xff0c;所以建议大家在学习时安装较新的版本&#xff0c;…
阅读更多...
高阶数据结构-图

高阶数据结构-图

高阶数据结构-图 图的表示 图由顶点和边构成&#xff0c;可分为有向图和无向图 邻接表法 图的表示方法有邻接表法和邻接矩阵法&#xff0c;以上图中的有向图为例&#xff0c;邻接表法可以表示为 A->[(B,5),(C,10)] B->[(D,100)] C->[(B,3)] D->[(E,7)] E->[…
阅读更多...
Ribbon：负载均衡及Ribbon

Ribbon：负载均衡及Ribbon

什么是负载均衡&#xff1f; 第一种轮询算法&#xff0c;依次遍历去执行&#xff0c;达到负载均衡 集成Ribbon 导入pom&#xff0c;在消费者服务里的pom文件导入 <!-- Ribbon 集成 --><!-- https://mvnrepository.com/artifact/org.springframework.cloud/spr…
阅读更多...
-Webkit-Box 在 Safari 中出现的兼容性问题

-Webkit-Box 在 Safari 中出现的兼容性问题

一、问题背景&#xff1a; UI要求要实现这样的效果&#xff0c;使用 display:-webket-box在chrome浏览器下完美解决 但是马上啪啪打脸&#xff0c;在safari浏览器下显示空白 &#xff0c;不能不说浏览器之间的兼容性简直就是天坑 二、解决办法 通过浏览器调试发现原本float的…
阅读更多...
[机器学习]特征工程：主成分分析

[机器学习]特征工程：主成分分析

目录 主成分分析 1、简介 2、帮助理解 3、API调用 4、案例 本文介绍主成分分析的概述以及python如何实现算法&#xff0c;关于主成分分析算法数学原理讲解的文章&#xff0c;请看这一篇&#xff1a; 探究主成分分析方法数学原理_逐梦苍穹的博客-CSDN博客https://blog.csdn.…
阅读更多...
YOLOX算法调试记录

YOLOX算法调试记录

YOLOX是在YOLOv3基础上改进而来&#xff0c;具有与YOLOv5相媲美的性能&#xff0c;其模型结构如下&#xff1a; 由于博主只是要用YOLOX做对比试验&#xff0c;因此并不需要对模型的结构太过了解。 先前博主调试过YOLOv5,YOLOv7&#xff0c;YOLOv8,相比而言&#xff0c;YOLOX的环…
阅读更多...
RS232、RS422、RS485硬件及RS指令、RS2指令应用知识学习

RS232、RS422、RS485硬件及RS指令、RS2指令应用知识学习

RS232、RS422、RS485硬件及RS指令、RS2指令应用知识学习 一、串行&#xff08;异步/同步)通讯、并行通讯、以太网通讯 二、单工通讯/半双工通讯/双工通讯 三、常用硬件接口&#xff08;工业上基本是RS485两线制的接线&#xff09; 常用硬件接口RS232/RS422/RS485&#xff0c;…
阅读更多...
C#与西门子PLC1500的ModbusTcp服务器通信2--ModbusTcp协议

C#与西门子PLC1500的ModbusTcp服务器通信2--ModbusTcp协议

Modbus TCP是近年来越来越流行的工业控制系统通信协议之一&#xff0c;与其他通信协议相比&#xff0c;Modbus TCP通信速度快、可靠性高、兼容性强、适用于模拟或数字量信号的传输&#xff0c;阅读本文前你必须比较熟悉Modbus协议&#xff0c;了解tcp网络。 一、什么是Modbus …
阅读更多...
[golang gin框架] 46.Gin商城项目-微服务实战之后台Rbac客户端调用微服务权限验证以及Rbac微服务数据库抽离

[golang gin框架] 46.Gin商城项目-微服务实战之后台Rbac客户端调用微服务权限验证以及Rbac微服务数据库抽离

一. 根据用户的权限动态显示左侧菜单微服务 1.引入 后台Rbac客户端调用微服务权限验证功能主要是: 登录后显示用户名称、根据用户的权限动态显示左侧菜单,判断当前登录用户的权限 、没有权限访问则拒绝,参考[golang gin框架] 14.Gin 商城项目-RBAC管理,该微服务功能和上一节[g…
阅读更多...
攻防世界-simple_php

攻防世界-simple_php

原题 解题思路 flag被分成了两个部分&#xff1a;flag2&#xff0c;flag2。获得flag1需要满足变量a0且变量a≠0&#xff0c;这看起来不能实现&#xff0c;但实际上当变量a的值是字符时&#xff0c;与数字比较会发生强制类型转换&#xff0c;所以a为字符型数据即可&#xff0c;变…
阅读更多...
最新文章

Copyright @ 2022~2023