【leetcode】动态规划::前缀和（二）

标题：【leetcode】前缀和（二）

@水墨不写bug

---

 正文开始：

（一） 和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

 思路一：

        暴力求解，按照题目的描述来求解，对于每一个数，依次向后求和，如果和==k，此时不能停下来，ret++继续遍历到整个数组。很显然，此算法时间复杂度O(N^2)，显然是会超时的算法。

思路二：

        我们可以换一种思路，现在我们聚焦于以下标 i 为结尾的和为k的数组，它们可能存在一个或者多个，甚至根本不存在；这时，我们已经固定了一个下标i，只需找到另一个下标即可；假设 i 之前存在一个下标 i0，[ i0 , i ](闭区间)的区间和为 k ，这时算出 以 i 为结尾的前缀和 sum[i]，这就将问题：i之前是否存在i0，使得[ i0 , i ](闭区间)的区间和为 k —转化为了—> 下标 i 之前是否存在 i0 使得 i0 的前缀和为 sum[i] - k；

        这时如果你就按照以上思路来建立前缀和数组，然后使用数组时你就会后悔自己做过的事情了：在使用前缀和数组的时候，对于一个指针cur = i，需要向前遍历数组，在cur向后移动后，还要进行向前遍历，这个操作的时间复杂度为O(N^2),再加上建立前缀和数组的O(N),时间复杂度不减反增！

        这时我们就需要考虑，一些操作是否能够同时进行：将for的嵌套优化为一个for循环即可解决的问题。

        如何理解呢，其实一些互不影响的操作可以可以同时进行，这时我们就可以在同一个循环中同时进行多个操作，以此来减少for循环的个数，以此来降低时间复杂度。

        在本题中，由于前缀和前n项和在每次循环中只使用一次，所以可以创建一个变量，通过对变量进行迭代累加求和，来代替前缀和数组。

        sum是不断变化的，此时创建一个哈希表，目的是用来记录此时sum的值，在向后遍历时，sum会递增。

        创建变量ret累计和为k的字符串的个数；

        sum记录第i项的前缀和；

        创建hash表，用来向前找（sum-k）时 ret 累加 答案（sum-k）的个数。

参考代码： 

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;int ret = 0,sum = 0;hash[0] = 1;for(auto x:nums){sum+=x;if(hash.count(sum-k)) ret += hash[sum-k];hash[sum]++;}return ret;}
};

（二）可被K整除的子数组

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。

子数组 是数组的 连续 部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0%k] = 1;int sum = 0,ret = 0;for(const auto& e : nums){sum += e;//计算前缀和//判断是否有符合要求的前缀和int aim = (sum%k+k)%k;if(hash.count(aim)) ret += hash[aim];hash[aim]++;}return ret;}
};

（三）连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;//存前缀和与对应的下标hash[0] = -1;for( auto& e:nums) if(e == 0) e--;int ret = 0,sum = 0,n = nums.size();for(int i = 0;i < n;i++){sum += nums[i];if(hash.count(sum)) ret = max(ret,i-hash[sum]);else hash[sum] = i;}return ret;}
};

---

完~

未经作者同意禁止转载