您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

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

题目概述

解题思路

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

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进