解法一：暴力解法

此题需要求解连续子数组元素的和等于目标值的最长子数组长度，因此需要两个变量分别确定子数组的头和尾。

暴力解法的思路如下：定义两个变量i、j，分别表示当前子数组的头尾。其中，i指针从第0个位置开始遍历，用来表示子数组的头；j指针从i开始遍历，表示子数组的尾。在遍历过程中，若求得当前子数组的和等于目标值，则将结果与res比较并更新（如果大于res），否则继续遍历。

根据上述思路，实现的代码如下：

注意：该方法复杂度较高，会超出运行时间限制。

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 res = 0; // 存放结果
        for (int i = 0; i < arr.size(); i ++) {
            int cur = 0; // 每次内层循环结束时，当前和置为0
            for (int j = i; j < arr.size(); j ++) {
                cur += arr[j]; // 当前和
                if (cur == k) { // 找到目标值
                    res = max(res, j - i + 1); // 更新结果
                }
            }
        }
        return res; 
    }
};

解法一使用了两层循环进行遍历，时间复杂度为；该方法并未使用额外空间，空间复杂度为。

解法二：前缀和+哈希表

解法二采用前缀和以及哈希表的思路对解法一的时间复杂度进一步优化，具体而言：（如下图所示）

  1. 定义前缀和数组preSum（大小为n + 1，其中n为原数组长度），并遍历原数组，其中表示：

  2. 在构建完preSum后，有（设i < j）：


    故有： 到区间数字的求和为:

    因此，题目可转换为：原题所述「原数组区间和」转变为「preSum数组某两个数之差」，可利用“两数之和”题目（题解链接https://blog.nowcoder.net/n/40f190e83cf74629b8f5effd3ce2d410
    ）思路进行求解：

    1. 哈希表具有「空间换时间」的作用，因此先定义哈希表hash，并做如下映射：

    （即做”前缀和“到”下标“之间的映射）

    注意：

    • 在构建哈希表过程中，仅当「preSum[i]未出现在哈希表中时，才将其添加到哈希表中」，目的是：记录「第一次出现该前缀和的位置」。
    • 需要完成初始化：hash[0] = 0，目的是：考虑原数组第0个元素也被用到：读者可自行考虑案例：

    1. 在构建完hash后，从后到前遍历preSum数组，其中target = preSum[i] - k即为在哈希表中要查找的数，若找到，更新res，否则继续向前遍历。

图片说明

图片说明

图片说明

图片说明

根据上述思路，实现代码如下：

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; 
        unordered_map <int, int> hash; // 定义哈希表
        hash[0] = 0; // 初始化哈希表
        int n = arr.size(); 
        vector<int> preSum(n + 1, 0); // 定义前缀和数组
        for (int i = 1; i <= arr.size(); i ++) {
            preSum[i] = preSum[i - 1] + arr[i - 1]; // 求前缀和
            if (hash.find(preSum[i]) == hash.end()) // 如果表中不存在
                hash[preSum[i]] = i; 
        }
        int res = 0; 
        for (int i = n; i >= 0; i --) { // 遍历原数组
            int target = preSum[i] - k; 
            if (hash.find(target) != hash.end()) { // 找到
                res = max(res, i - hash[target]); // 更新res
            }
        }
        return res; 
    }
};

该方法先后遍历了两次数组，时间复杂度为；该方法定义了preSum数组以及哈希表，空间复杂度为。

解法二优化：

解法二定义了前缀和数组preSum，然而，可以在构建哈希表的同时记录“到当前位置的前缀和”，无需额外定义preSum数组。

此方法大致思路同解法二，但写法略有不同，实现代码如下：

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; 
        unordered_map <int, int> hash; // 定义哈希表
        hash[0] = -1; // 初始化哈希表
        int n = arr.size(), res = 0, preSum = 0; 
        for (int i = 0; i < arr.size(); i ++) {
            preSum += arr[i]; // 到当前位置的前缀和
            if (hash.find(preSum) == hash.end()) // 哈希表中未找到
                hash[preSum] = i; 
            int target = preSum - k; // 需要在哈希表中查找的值
            if (hash.find(target) != hash.end()) // 找到
                res = max(res, i - hash[target]); // 更新res
        }
        return res; 
    }
};

该方法仅遍历一次数组，时间复杂度为，优于解法二；该方法定义了哈希表，空间复杂度为，但不用定义preSum数组，空间复杂度小于方法二。