方法一：暴力（超时）

1.解题思路

题意：
对于一个给定的数组，数组元素有正有负有0，求所有连续子数组元素和为k中，最长的子数组。

2.解法

暴力解法为两层循环遍历序列，分别枚举左右端点。对子数组累加求和为k的保存并比较其长度，从而得到最长子序列的长度。

3.具体代码

class Solution {
public:
    /**
     * max length of the subarray sum = k
     * @param arr int整型vector the array
     * @param k int整型 target
     * @return int整型
     */
    int maxlenEqualK(vector<int>& arr, int k) {
        if(arr.empty())return 0;
        int ans=0;
        for(int i=0;i<arr.size();i++){//子数组左端点 
            int sum=0;
            for(int j=i;j<arr.size();j++){//累加求和 
                sum+=arr[j];
                if(sum==k)ans=max(ans,j-i+1);//若找到等于k，则更新最大长度 
            }
        }
        return ans; 
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：，两层循环遍历长度为n的序列
空间复杂度：，仅用到了两个int型变量sum，ans，来记录长度。

方法二：哈希表

1.解题思路

根据累加求和的思想，可以先记录序列中的前n项和，再做差得出子数组和。因为先找子序列和，再找子序列长度进行比较，所以可以把子序列和与数组元素下标做出映射关系，这里选用unordered_map，不用对容器内元素进行排序。

2.解法

• i为遍历的当前元素下标，即要做子数组的前一个元素的下标
• sum[i]即为要做子数组的前一个元素的前n项和
• sum[i]+k即为要找子数组的右端点的前n项和
• m[sum[i]+k]即为要找子数组的右端点的下标
• m[sum[i]+k]-i即要找子数组的长度

但是，这种方法只考虑到了要找子数组从第二个元素开始的情况
所以，最后要加上要找子数组从第一个元素开始的情况

3.图解

4.具体代码

class Solution {
public:
    /**
     * max length of the subarray sum = k
     * @param arr int整型vector the array
     * @param k int整型 target
     * @return int整型
     */
    int maxlenEqualK(vector<int>& arr, int k) {
        if(!arr.size())return 0;
        vector<int>sum(arr.size(),0);//保存前n项和
        unordered_map<int,int>m;//前n项和，对应的下标，unordered_map不用按键排序     
        sum[0]=arr[0];//计算sum的值 
        int size=arr.size();
        for(int i=0;i<size;i++){
            sum[i]=sum[i-1]+arr[i];
            m[sum[i]]=i;//map查找键方便，我们从子数组和推出对应端点下标 
        } 
        int ans=0;
        for(int i=0;i<size;i++){
            if(m.find(sum[i]+k)!=m.end())ans=max(ans,m[sum[i]+k]-i);//由前n项和在map中找出刚好大k的，即右端点 
        } 
        if(m.find(k)!=m.end())ans=max(ans,m[k]+1);//如果有前n项和为k，即子数组为前n项的，再比下ans 
        return ans;
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：，n是序列长度，因为仅遍历了两次序列。
空间复杂度：，需要存储长度为n的哈希表完成前缀合与子序列下标的映射。