和为K的子数组--前缀和优化

0x01.问题

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

• 数组的长度为 [1, 20,000]。
• 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

0x02.详细分析思路

• 初读题目，发现主要是寻找子数组的个数，条件是子数组的和为k。

• 发现是子数组问题，于是各种方法就可以大显神通了，dp，优化dp，滑动窗口等等。

• 最为简单粗暴的肯定是两层循环，遍历所有的子数组，但是肯定不是一个好办法，而且这里数组长度达到了20000，肯定不可取。

• 我们知道，一般使用dp等思路都是在对暴力思路优优化的基础上产生的，我们详细思考一下如何去优化：

  • 思考一：我们使用双循环遍历的主要目的？

    • 主要是得到所有子数组的和，力求遍历到所有可能。

  • 思考二：你是否觉得这样遍历过于浪费，因为实际上很多都是一样的数在遍历。

  • 思考三：思考二产生的原因是什么？

    • 原因就是子数组的开头不同，造成一旦更换了子数组的开头，就需要重复遍历。

  • 思考四：能否快速得到一个连续子数组的和？

    • 相信这个肯定好办，[3,6]这个子数组怎么得到，是不是[0,6]-[0,2]。
    • 发现上面这个思路，一切都好办了，因为我们不需要遍历所有子数组可能的开头了，因为它们的和都可以巧妙的转换一下。

  • 思考五：对于思考四，如果要具体实现，需要维护什么样的值？

    • 我们发现，都用到了一个[0,i]的数组值，所以我们需要实时的维护一个pre，它的和为[0,i]的和，这其实也就是前缀和。

  • 思考六：对于思考四，我们如何得到和为k的子数组个数。

    • 由于维护了pre，所以我们只需要知道pre以前是否等于过现在的pre-k，以及等于的次数，这个数组就需要记录了，我们可以维护哈希表<Interger,Integer>表示pre出现的次数。
    • 这样，我们每次更新pre后，将pre以及出现的次数存入哈希表，如果pre-k在表中，取出累加即可。

  • 思考到这，整个算法的优化思路已经出来了。

• 具体的算法：

  （1）维护pre表示子数组[0,i]的和。
  （2）维护哈希表，其中键是pre，值是pre出现的次数。
  （3）从做往右扫描原数组，如果pre-k存在表中，取出相应的值进行累加。

0x03.解决代码–前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count=0;
        int pre=0;
        HashMap<Integer,Integer> hash=new HashMap<>();
        hash.put(0,1);
        for(int i=0;i<nums.length;i++){
            pre+=nums[i];
            if(hash.containsKey(pre-k)){
                count+=hash.get(pre-k);
            }
            hash.put(pre,hash.getOrDefault(pre,0)+1);
        }
        return count;
    }
}

ATFWUS --Writing By 2020–05-15