博客

题目概述

解题思路

这道题的难点在于，如何将时间复杂度控制在O(N)。我开始想到用前缀和数组去解决，因为只要用前b个元素的和减去前a个元素的和，就能得到从(a+1)到b这个子树组之和，便于我们去访问各种加和的情况；但是再往下就没有头绪了。

于是参考了左神的做法，采用一个hash map来记录从第1个元素累加到第 i 个元素的和sum_i 的值，作为key值；而sum_i 首次出现对应的 i 值则是它的value。接下来就好办了，当我们遍历到第 i 个元素时，只需要算两步：

• 首先是这个值sum_i 是否等于目标值tgt
• 其次是sum_i – tgt 这个值是否在hash map中出现过，如果出现过且对应的序号为 s，则比较当前的最长子树组长度max_len和 i – s的值来更新max_len

方法的时间复杂度和空间复杂的都是O(N)。

方法性能

示例代码

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) 
    {
        // write code here
        unordered_map<int, int> sum_L;
        int res_len = 0, len = arr.size(), sum_i = 0;

        for(int i = 0; i < len; ++i)
        {
            sum_i += arr[i];
            if(sum_i == k)
                res_len = max(res_len, i + 1);
            if(sum_L.find(sum_i) == sum_L.end())
            {
                sum_L[sum_i] = i;
            }
            if(sum_L.find(sum_i - k) != sum_L.end())
            {
                res_len = max(res_len, i - sum_L[sum_i - k]);
            }
        }

        return res_len;
    }
};