牛客题霸. 未排序数组中累加和为给定值的最长子数组长度

本文主要是介绍牛客题霸. 未排序数组中累加和为给定值的最长子数组长度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目概述

解题思路

这道题的难点在于，如何将时间复杂度控制在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;
    }
};

这篇关于牛客题霸. 未排序数组中累加和为给定值的最长子数组长度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！