当前位置：首页 > news >正文

深圳网站制作公司深圳app开发装修设计软件3d

news 2025/9/17 23:28:25

深圳网站制作公司深圳app开发,装修设计软件3d,xiaohua wordpress主题,做国外有那些网站Halo，这里是Ppeua。平时主要更新C，数据结构算法，Linux与ROS…感兴趣就关注我bua！ 和为K的子数组题目:示例:题解：解法一:解法二: 题目: 示例: 题解： 解法一: 暴力解法:我们很容易想到通过两个for循环去遍…

在这里插入图片描述
Halo，这里是Ppeua。平时主要更新C++，数据结构算法，Linux与ROS…感兴趣就关注我bua！

和为K的子数组

题目:
示例:
题解：
- 解法一:
- 解法二:

题目:

在这里插入图片描述

示例:

在这里插入图片描述

题解：

解法一:

暴力解法:我们很容易想到通过两个for循环去遍历数组中所有和的可能,之后来判断有几个满足K.他的代码十分的简单,所以这里直接给出.

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;for (int start = 0; start < nums.size(); ++start) {int sum = 0;for (int end = start; end >= 0; --end) {sum += nums[end];if (sum == k) {count++;}}}return count;}
};

这里通过一个start与end来控制子数组区间.若为K则计数++.

我们仔细观察这样的做法.可以很容易的发现,**我们可以通过前缀和来解决两层循环的问题.**于是就有了解法二:利用前缀和来解决此类问题.

解法二:

不熟悉前缀和的uu们可以看看这篇文章:[前缀和]((138条消息) 【高精度加减乘除法、一维二维前缀和&&差分】思路讲解及代码实现_ppeua的博客-CSDN博客)

这里就直接开始推导了,这里利用的是一维的前缀和方法.

定义:**pre[i]**表示从0~i的所有数组元素之和.

那么根据前缀和的定义:j~i区间内的元素之和可以表示为:pre[i]-pre[j-1],我们要判断的就是这个结果能不能等于K.

所以现在的求解就简化为下面这个式子:
在这里插入图片描述

我们对两边式子进行简单的数学推导可以得到.

在这里插入图片描述

这样我们可以通过一个hash来存储值,之后只要验证当前遍历的这个前缀和-k的结果是否出现在hash当中.若出现则+上其出现的次数.

代码较为简单:

class Solution {
public:int subarraySum(vector<int>& nums, int k) {for(int i=1;i<nums.size();i++){nums[i]+=nums[i-1];}unordered_map<int,int>mp;mp[0]=1;int res=0;for(int i=0;i<nums.size();i++){if(mp.find(nums[i]-k)!=mp.end()){res+=mp[nums[i]-k];}mp[nums[i]]++;}return res;}
};