【专题四】前缀和（2）

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

724. 寻找数组的中心下标

个人解

思路：

暴力解法：需要遍历整个数组，然后对于每一个数，需要再遍历一遍，计算左右两边的数之和然后再比较，时间复杂度：O($n^2$)

利用前缀和数组：

• 建立一个前缀和数组，dp[i] 表示数组 nums[1] - nums[i] 的元素之和
• 每次判断是不是中心下标就用dp[n] - dp[i] == dp[i] - nums[i] 判断

用时：7:00
屎山代码：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {

        int n = nums.size();
        vector<int> dp(n + 1, 0);
        // 初始化前缀和数组
        for(int i = 1; i <= n; i++)
        {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= n; i++)
        {
            if(dp[n] - dp[i] == dp[i] - nums[i - 1])
                return i - 1; 
        }
        return -1;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

238. 除自身以外数组的乘积

个人解

思路：

• 建立两个数组，一个前缀积数组，一个后缀积数组（不包括 i 位置的元素）,这两个数组没必要多开一个空间
• 前缀积数组：dp1[i] 代表 nums[0, i - 1] 的乘积
• 后缀积数组：dp2[i] 代表 nums[i + 1, n - 1] 的乘积
• 计算：dp1[i] = dp1[i - 1] * nums[i - 1] （填表顺序，正着填）
• 计算：dp2[i] = dp2[i + 1] * nums[i + 1]（填表顺序，倒着填）
• 边界问题：我们容易发现：当i == 0时，[i - 1]越界访问，i == n - 1时也越界访问。对此，我们只需要先自行观察初始化一下这两个位置就行了。因为两个位置的两边都没有元素且为了不影响后面的乘积，只需将两个位置都初始化成1即可

用时：20:00
屎山代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0), dp1(n, 1), dp2(n, 1);
        // 初始化数组
        for(int i = 1; i < n; i++)
            dp1[i] = dp1[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)  // 从哨兵位的下一个位置开始初始化
            dp2[i] = dp2[i + 1] * nums[i + 1];
        for(int i = 0; i < n; i++)
        {
            ans[i] = dp1[i] * dp2[i];
        }
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

560. 和为 K 的子数组

个人解

这道题可不能双指针，因为数组里面有可能有负值

思路：

建立一个前缀和数组，dp[i] 表示 nums[0, i - 1]位置的元素和。
然后遍历数组，得到所有的子数组，然后利用上面的前缀和数组来求对应子数组的元素和。
但是时间复杂度为：O($n^2$ + $n$)，所以我就不实现了，感觉方法不行。

优质解

前缀和 + 哈希表

• 用i表示当前遍历到的位置，用x表示i之前的位置。
• 往前找以i为尾的子数组[x, i]有多少个和为k的，也就是dp[i] - dp[x] == k
• 又因为，这道题只让我们求个数，所以我们没必要面对不同的i都去遍历一遍i前面的x来获取dp[x]查看是否符合。
• 我们只需要用一个哈希表map<前缀和值，次数>来记录i之前所出现的不同前缀和出现的次数，到了位置i查找满足 dp[x] == dp[i] - k的dp[x]有多少个。
• 另外，我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于dp[i] - k 。因此，我们仅需用⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数
• 细节问题：因为有可能当前的前缀和 == k，但是，哪怕是dp[i] - dp[0]代表的也只是：nums[1 , i]的所有元素的和。我们没有能代表nums[0, i]所有元素的和，所以我们要先储存一个前缀和0

代码：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int, int> dict;
        dict[0] = 1;
        int ans = 0, sum = 0; // 用 sum 表示dp[i] 位置的前缀和
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if(dict.count(sum - k))
                ans += dict[sum - k];
            dict[sum]++; // 当前的前缀和值，次数 + 1
        }
    return ans;
    }
};

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！