?xml version="1.0" encoding="UTF-8"?
欢迎关注本人的微信公众号AI_Engine
如期而至，leetcode系列第二篇~
题目：
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
示例 1:
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:
输入:nums=[-2, -1, 2, 1],k=1
输出:2
解释:子数组[-1, 2]和等于 1，且长度最长。
答案：
分析：
这道题主要考察数组前缀和的理解和作用，因为利用前缀和我们可以快速的计算出数组中某个子数组的和。那么前缀和究竟是什么概念呢？简单的说就好比有一个数组A，然后我们新建一个数组B，其中数组B中每一项B[i]保存A中[0…i]的和。那么对应的就会有前缀积，后缀和，后缀积。回到这道题目，我们可以使用两个for循环对该问题进行暴力破解，但是这不是leetcode（或者面试官们）想要的答案。那么面对诸如此类的问题我们就可以考虑使用前缀和方法以及哈希完成低时间负责的操作。我们以示例1（nums = [1, -1, 5, -2, 3], k = 3）来图解分析下：
数组A为原数组nums，B为A的前缀数组，为了方便理解与计算我们将前缀数组的头部加上一个元素，并设定为0，这样最终的前缀数组就是右边的样子了（可以理解吧，如果你不明白为什么加上一个0，往后面看），现在我们来看一下如何利用前缀数组解答这道题目。我们首先对这道题目降维，就是说我们先去求出nums数组中哪段子数组的和为K，依然图解：
这幅图的意思是：假设有一个包含7个元素的数组，索引为0-6。我们可以求出每个元素对应的前缀和sum（index=1是，可以求出sum1）。如果当我们计算到sum5时发现sum5与k值只相差sum1，那么就可以证明2-5的和就是K值，就是我们要的子数组。即：sum5 = sum1 + k =====> sum5 - k = sum1。但是我们怎么保证能够发现之间的前缀有sum1呢？这时候哈希表就派上用场了，我们将sum作为key，将index作为value，这样就可以把前缀数组中的元素按照顺序记录下来了。现在我们对题目进行升维：找到满足条件的最长的子数组。很简单，上述代码中diff_sum其实就是命中的sum-k，也是前缀数组中的某个元素。根据当前索引和哈希表中的索引就可以计算出长度，然后比较就可以了。为什么要在前缀数组中虚拟的添加一个0元素呢（代码里体现在res[-1]= 0)？这是因为如果某个sum-k = 0,即当sum = k时，那么此时最长的子数组一定是从数组的0索引开始计算的，但是如果数组的第一个元素不是0，那么哈希表中记录的前缀数组就不能包含0元素，这样我们就找到diff_sum,所以为了方便计算我们对哈希表进行虚拟添加元素res[-1] = 0,这样不仅方便计算，也能便于理解。
最后让我秀一下结果吧：
