和为K的子数组

迷南。 2024-04-07 16:07 70阅读 0赞

给定一个数组在给定一个整数，我们如何找出数组中和为这个整数的子数组呢？

**问题**

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

**方法**

前缀和：

前缀和是一种预处理，用于降低查询时的时间复杂度。举个例子：给定n个整数，然后进行n次询问，每次询问求一个区间内值的和。

创建一个字典dict，从第一位依次求和，即第一次求和是第一个数，第二次求和是第一和第二个数的和，第三次求和是一到三位数的和，以此类推。计算每一次的和出现次数，在字典中，和设为value，出现的次数设为key。在计算时，用每一次的和cur-sum减去k，再查找字典dict，中cur-sum - k值出现的次数，累加并返回，即为和为k 的连续子数组的个数。

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单 1

<table> 
 <tbody> 
  <tr> 
   <td>classs Solution:<br>def subrraySum(self,nums:List[int],k:int) -&gt; int:<br> &nbsp; &nbsp;cur_sum=0<br> &nbsp; &nbsp;dict={}<br> &nbsp; &nbsp;dict[0]=1<br> &nbsp; &nbsp;count=0<br> &nbsp; &nbsp;for num in nums:<br> &nbsp; &nbsp; &nbsp; &nbsp;cur_sum+=num<br> &nbsp; &nbsp; &nbsp; &nbsp;if cur_sum - k in dict:<br> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count+=dict[cur_sum - k]<br> &nbsp; &nbsp; &nbsp; &nbsp;if cur_sum in dict:<br>dict[cur_sum]+=1<br> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else:<br>dict[cur_sum]+=1<br> &nbsp; &nbsp; &nbsp; &nbsp;return count</td> 
  </tr> 
 </tbody> 
</table>

**结语**

针对和为K的子数组问题，提出前缀和的方法，证明该方法是有效的，是否还有其他方法呢？是我们值得思考的，必然存在其他方法也能去解决，需要自己不断探索。