【前缀和】--- 初阶题目赏析
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-k
ump[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. 前缀和算法也可以通过转化问题来解决类似子数组的问题。