【前缀和】--- 初阶题目赏析

2024-08-30 11:52
文章标签 题目 初阶 前缀 赏析

本文主要是介绍【前缀和】--- 初阶题目赏析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:       9ilk

(๑•́ ₃ •̀๑) 文章专栏:    算法Journey  


了解完一维和二维前缀和模板之后,我们来看几道题目感受前缀和的算法原理以及使用场景。


🏠 寻找数组的中心下标

📌 题目解析

寻找数组的中心下标

  • 1 <= nums.length <= 10^4。
  • 如果不存在中心下标则返回-1,有多个中心下标返回最左边的哪个。

📌 算法原理

✏️ 思路一

获取dp前缀和数组,dp[i]用来表示[1,i]区间内数组值之和,由于中心下标是左边区间元素之和 == 右边元素之和,中心坐标不包括在那,所以我们可以先获取前缀和数组,遍历数组,当dp[i-1](左边区间) == dp[n] - dp[i](右边区间),返回中心坐标.

注: 设立变量pos为-1,如果没找到中心下标,直接返回pos.

参考代码 :

class Solution {
public:int pivotIndex(vector<int>& nums) {//获取前缀和数组int n = nums.size();vector<int> v(n+1,0);vector<int> dp(n+1,0);for(int i = 1 ; i <= n ; i++){v[i] = nums[i-1];dp[i] = dp[i-1] + v[i]; }//使用前缀和数组int pos = -1;for(int i = 1 ; i <= n ; i++){if(dp[i-1] == dp[n] - dp[i]) //左 == 右{pos = i;return pos;}}return pos; //没找到中心下标}
};

✏️ 思路二

我们的目的是找一个点,它能左右两边区间和相等.由于前缀和算法本质是快速求一段连续区间 的和,本题中右边区间也是一段连续的和,因此我们可以分别求一个前缀和数组f和后缀和数组g来表示左边区间和右边区间。f[i]表示前缀和数组,即【0,i-1】区间数组的和,由此可得f[i] = f[i-1] + nums[i-1] ; g[i]表示后缀和数组,即【i+1,n-1】区间数组的和,由此可以得到g[i] = g[i+1] + nums[i+1].

参考代码 :

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int>  front(n,0); //[0,i-1]vector<int> back(n,0);//[i+1 ,n-1]//获取前缀和数组for(int i = 1; i < n ; i++){front[i] = front[i-1] + nums[i-1];}//获取后缀和数组for(int i = n-2 ; i>= 0 ;i--){back[i] = back[i+1] + nums[i+1];}int pos = -1;for(int i = 0 ; i < n ; i++){if(front[i] == back[i])//前缀 == 后缀{ pos = i;break;}}return pos;}
};

注 : 为防止越界,我们将f[0]设置为0,g[n-1]设置为0,因为他们都是边界前面和后面都没有数。

🏠 和为K的子数组

📌 题目解析

和为K的子数组

  • 子数组即数组中非空的连续序列。
  • 1 <= nums.length <= 2 * 10^4
  • -10^7 <= k <= 10^7

📌 算法原理

✏️ 思路一 : 暴力枚举

暴力解法思路很简单,就是两层for循环,记录sum,当sum为k时计数,当本题数组长度较长且数据范围较大,一定是会超时的。

注:本题不能用双指针或滑动窗口做优化,因为left,right的走向不一定是一直同向的,因为数组中可能有0和负数

✏️ 思路二 : 前缀和

1. 当我们遍历到某个位置i时,假设sum[i]为位置i的前缀和([0,i]区间数组和),此时要想求和为k的子数组,就转化成在[0,i]区间内找哪个位置的前缀和正好等于sum[i] - k

2.以i位置为结尾的所有子数组:也就是在遍历数组的过程中,在以i为结尾的区间看是否有哪一段前缀和正好等于sum[i] - k。从整个数组来看,这种做法是囊括所有和为k的子数组的情况的,因为子数组终究是原来整个数组的一部分,我们取以i位置为结尾的子数组观察,这样和为k的部分一直是新数组的右边的部分,不可能在中间部分不用回退了,而且这部分一直不断前进,这就使得当观察某个i位置结尾子数组时,只要它里面有等于k的那段,有几段就能找出几段sum-k。

3.sum[i]的记录:我们没有必要真的去弄一个前缀和数组,只需要一个变量sum来标记前一个位置的前缀和即可。

4. 如何判断以i位置为结尾的子数组内有sum - k:当每次遍历时,每计算一次i位置前缀和,我们就可以放进哈希表计数,这样就能进行计数有几个前缀和等于sum-k。但要注意的是,在计算i位置之前哈希表里面只保存【0,i-1】位置的前缀和。

5. 如果以i位置为结尾的区间正好和为k:此时本身就满足和为k的子数组,我们只需要让hash[0] = 1即可(表示不同位置正好本身为k的情况)。

参考代码:

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int> ump;int sum   = 0;  int count = 0;ump[0] = 1;for(int i = 0 ; i < n;i++){sum += nums[i];if(ump[sum-k]) count += ump[sum-k] ;//sum-kump[sum]++;//计算完后将sum[i]放进哈希表           }return count; }
};

🏠 除自身以外数组的乘积

📌 题目解析

除自身以外数组的乘积

📌 算法原理

✏️ 思路一:暴力解法

暴力解法就是固定某个位置将左边乘积算出,再将右边乘积算出即可,但时间复杂度是O(N^2)。

✏️ 思路二:前缀和

跟寻找数组中心下标一样,都要求的是左边右边两段连续区间:

1. 先预处理出前缀积和后缀积区间

f [ i ] = f[ i - 1 ] * nums[ i - 1 ] (前缀积)

g[ i ] = g[i + 1] * nums[ i +1 ] (后缀积)

2.使用两个数组:answer[i] = f[i] * g[i]

3.细节问题:与寻找数组中心下标那道题不同的是,我们这里要求的是积,因此边界都设置为1,这样相当于没乘。(f[0] = 1,g[n-1] = 1)

参考代码:

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> answer(n);vector<int> front(n,1);//前缀积数组 [0,i-1]vector<int> back(n,1);//后缀积数组  [i+1,n-1] for(int i = 1 ; i < n ;i++){front[i] = front[i-1] * nums[i-1];}for(int i = n-2;i>=0;i--){back[i] = back[i+1] * nums[i+1];}for(int i = 0 ; i < n ; i++){answer[i] = front[i] * back[i];} return answer;}
};

总结:

1. 前缀和是一种思想并不是一定是要求和,本质快速求某一段区间的某个性质。

2.对于前缀和数组边界情况的要灵活处理,同时一段连续区间并不一定就是求前缀,后缀也是一段连续区间。

3. 前缀和算法也可以通过转化问题来解决类似子数组的问题。

这篇关于【前缀和】--- 初阶题目赏析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1120749

相关文章

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

JAVAEE初阶第七节(中)——物理原理与TCP_IP

系列文章目录 JAVAEE初阶第七节(中)——物理原理与TCP_IP 文章目录 系列文章目录JAVAEE初阶第七节(中)——物理原理与TCP_IP 一.应用层重点协议)1. DNS2 .NAT3. NAT IP转换过程 4 .NAPT5. NAT技术的缺陷6. HTTP/HTTPS7. 自定义协议 二. 传输层重点协议 1 .UDP协议 2.1.1 UDP协议端格式 2.1.2 UD

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

msyql执行效率的问题以及常见基础面试题目

SQL被称为结构化查询语言(Structured Query Language )是操作和检索关系型数据库的标准语言 SQL语言包括三种主要程序设计语言类别的语句:数据定义语言(DDL),数据操作语言(DML)及数据控制语言(DCL)。 ※ 数据定义语言(DDL),例如:CREATE、DROP、ALTER等语句。    Data Definition Language ※ 数据

前缀和 — 利用前缀信息解决子数组问题

【前缀和的核心思想是预先处理数组来快速计算任意子数组的和,基本上用于数组和序列问题。】 前缀和算法具体步骤 构造前缀和数组: 给定一个数组nums,其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前缀和公式: p r e x [ i ] = n u m s [ i ] ( i = = 0 ) p r e x [ i ] = p r e x