325.Maximum Size Subarray Sum Equals k

题目

给一个数组nums和目标值k，找到数组中最长的子数组，使其中的元素和为k。如果没有，则返回0。

• 输入: nums = [1, -1, 5, -2, 3], k = 3
• 输出: 4
• 解释: 子数组[1, -1, 5, -2]的和为3，且长度最大

挑战

尝试使用 O(n) 的时间复杂度完成

思路

hashMap + prefixSum

解法

from typing import (
    List,
)

class Solution:
    """
    @param nums: an array
    @param k: a target value
    @return: the maximum length of a subarray that sums to k
    """

    def max_sub_array_len(self, nums: List[int], k: int) -> int:
        # Write your code here
        size = len(nums)
        s = [0] * (size + 1)
        restDic = {}
        ans = 0


        for i in range(0, size + 1):
            if s[i] in restDic:
                # 等充会员后验证下
                ans = max(ans, i - restDic[s[i]])
            if s[i] == k:
                # pre sum 的下标为当前下标数组的长度值，故不需要加一
                ans = max(ans, i)

            if i < size:
                s[i + 1] = s[i] + nums[i]
                right = k + s[i]

                if  right not in restDic:
                    # restDic 的 key 值是 pre sum 的 right 数值，value 值是 nums 当前 index 值
                    restDic[right] = i

        return ans

复杂度分析

时间复杂度 O(N) 空间复杂度 O(N) N = preSumLength + hashKeyLength