【算法题解】325. 和等于 k 的最长子数组长度-一一网

这是我参与更文挑战的第4天，活动详情查看：更文挑战

题目

325. 和等于 k 的最长子数组长度

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

注意:
nums 数组的总和是一定在 32 位有符号整数范围之内的。

示例 1:

输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:

输入: nums = [-2, -1, 2, 1], k = 1
输出: 2
解释: 子数组 [-1, 2] 和等于 1，且长度最长。

思路1：暴力法

对于这道题，我们最直观想到的方法是，先找到数组的所有子数组，依次计算它们的和看是否为k，并记录出长度最大的那个。

找到所有的子数组需要进行双层循环，时间复杂度O(n^2)，求和复杂度O(n)，总时间复杂度O(n^3)，不是本题的最优解。

示例代码：

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        res = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if sum(nums[i:j+1]) == k:
                    res = max(res, j-i+1)
        return res
复制代码

思路2：前缀和

然后，我们尝试对暴力法进行优化，发现在对每个子数组求和的过程中，存在大量的重复运算。

我们可以用一个数组dp，来记录到当前位置的累加和，采用求差的思路来算出子数组的和，来节省我们求和过程中的重复计算。

举个例子，对于数组[1, -1, 5, -2, 3]，它的求和累加数组dp为[0, 1, 0, 5, 3, 6] (为了方便计算，多出了第一位，默认为0)

如果想要计算子数组nums[0:1], 即[1,-1]的和，只需计算dp[2] – dp[0] = 0,

如果想要计算子数组nums[1,4], 即[-1,5,-2,3]的和，只需计算dp[5] – dp[1] = 5.

这就是前缀和的方法，这样以后，使得求和的O(n)复杂度退化了O(1)的复杂度，提高了运行效率。

代码总的时间复杂度取决于双层循环，总时间复杂度为O(n^2)

示例代码：

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        res = 0
        dp = [0] * (len(nums)+1)
        for i in range(1, len(nums)+1):
            dp[i] += dp[i-1] + nums[i-1]
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                s = dp[j+1] - dp[i]
                if s == k:
                    res = max(res, j-i+1)
        return res
复制代码

思路3：前缀和 + 哈希

我们继续思考，如何才能更加优化代码性能。

还记得“两数之和”吗？上面的前缀和的思路是不是跟两数之和很像，采用了双层循环，看子数组的和是不是等于目标值。

“两数之和”是怎么优化的，我们使用了一个集合，在遍历数组的时候，把元素放进这个集合里，同时看目标值k减去数组元素i的值，是不是在这个集合里，如果在的话，则能找到目标解，时间复杂度从O(n^2)退化成了O(n)。

所以这道题里，是否可以采用类似的思路呢？答案是可以的。

我们需要一个哈希表dic，哈希表的键就是数组和的累加值，哈希表的值就是该累加值对应的到达的数组下标。

在遍历数组时，我们判断当前累加值s，与目标值k的差值，即s-k，在不在哈希表的键里面，如果在的话，即证明在之前存在一个累加值s0，可以满足当前的累加值s减去s0为k，同时，我们根据哈希表的值以及当前遍历的数组元素的下标，计算出下标的差值，用于与最终结果进行比较并返回。

要注意题目中为了求最长的子数组长度，所以如果累加值存在于哈希表中，则哈希表不进行元素的更新，保证该键对应的值足够小，一边算出最大的长度。

举个例子，对于数组[1,-1,5,-2,3]，目标值为3，我来模拟一下全过程。

首先创建哈希表dic，并加入默认元素{0: -1}

遍历数组，累加元素，累加值1，下标0，dic变为{0:-1,1:0}，1-3=-2不在哈希表的键里
继续遍历，累加元素-1，累加值0，下标1，因0存在于dic, dic保持为{0:-1,1:0}，0-3=-3不在哈希表的键里
继续遍历，累加元素5，累加值5，下标2，dic变为{0:-1,1:0,5:2}，5-3=2不在哈希表的键里
继续遍历，累加元素-1，累加值3，下标3，dic变为{0:-1,1:0,5:2,3:3}，3-3=0在哈希表的键里，值为-1，即子数组[1, -1, 5, -2]满足题目要求，长度为4
继续遍历，累加元素3，累加值6，dic变为{0:-1,1:0,5:2,3:3,6:4}，6-3=3不在哈希表的键里

综上，答案为4

该思路只需要遍历一次数组，时间复杂度为O(n)

最终代码如下：

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        dic = {0: -1}
        res = s = 0
        for i in range(len(nums)):
            s += nums[i]
            if s - k in dic:
                res = max(res, i-dic[s-k])
            if s not in dic:
                dic[s] = i
        return res
复制代码