本文共 1367 字，大约阅读时间需要 4 分钟。
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 :
数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
思路：前缀和通俗地来说就相当于数组的前 n 项和，题目中要求的是连续的子数组，并且还是连续和为k的。
首先对于连续的子数组中的连续和，可以推出：sum( i , j ) = sum(0 , j )-sum( 0 , i )，其中sum( i , j )表示从索引 i 到 j-1 的所有元素的和。
根据这个条件，可以定义一个sum[ j ]数组表示nums数组的前 j 项和，那么上面这个条件就可以转换为：k = sum[ j ] - sum[ i ]，其中 k 就是要求的和。
但这样的话,对于每个 j，我们需要枚举所有的 i 来判断是否符合条件，这样虽然也可以的出结果，但时间复杂度是O(n^2)，n为数组的长度。
class Solution { public int subarraySum(int[] nums, int k) { int[] count = new int[nums.length]; int sum = 0; int result = 0; for (int i=0;i 那我们可不可以将该算法再优化呢？
上述代码中正是由于不知道对于每个 j，到底有多少个 i 是符合条件的( j < i )
我们可以将上述条件进行变形：sum[ i ] = sum[ i -1 ] + num[ i ] ：表示数组的前 i 项和可以由数组前 i-1 项和加上当前第 i 个数组成。
那么对于[ j…i ] 这个子数组和为 k这个条件我们可以转化为
sum[ i ] − sum[ j − 1 ]=k 通过简单的移项就可以得到 sum[ j - 1 ] = sum[ i ] - k那么我们就只需知道前n项和中有多少是等于sum[ i ] - k，就可以知道有多少个 j 是满足条件的，这里我们就可以构建一个哈希表，其中key就是前缀和（即数组前n项和），而value就是前缀和重复出现了多少次。
那么只需遍历一次数组，每次遍历时判断哈希表中是否存在等于sum[ i ] - k的值，如果有就将其键对应的值加到总数中，并更新哈希表中出现的次数。
class Solution { public int subarraySum(int[] nums, int k) { HashMap map = new HashMap (); //初始值<0,1>表示数组中存在一个整数n恰好等于k map.put(0,1); //前n项和 int sum = 0; //计数 int result = 0; for (int i=0;i 发表评论
最新留言
关于作者
