leetcode325-- Maximum Size Subarray Sum Equals k (Locked)

leetcode325-- Maximum Size Subarray Sum Equals k (Locked)

题目

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

之前做过一个求最大连续子数组等于k的个数的,现在是求这些里面最长的那一个,方法也是一样的,即每次遍历之前先查找,再建立字典,查找到了之后就要更新当前的最长的,但是要注意和直接为k的情况,这时候肯定是最长的,

def findMaxLength(nums,k):
    dic = {}
    res = 0
    summ = 0

    for i in range(len(nums)):
        summ += nums[i]
        if summ==k:
            res = max(res, i+1)
        
        if summ-k in dic:
            cur_length = i-dic[summ-k]
            res = max(res, cur_length)

        dic[summ] = i   # 注意如果中间的一段加起来和为0的话,重新更新字典也没事儿,因为前面的判断summ==k,也不会把最长的给漏掉,

上面的时间复杂度是O(n),

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦