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

难度: Medium

Submission

运行时间: 99 ms

内存: 57.9 MB

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        # 初始化哈希表，用于记录累积和及其对应的下标
        cumulative_sum = {0: -1}  # 累积和为0的下标是-1，用于处理从数组起始位置开始的子数组
        max_length = 0  # 最长连续子数组长度
        current_sum = 0  # 当前累积和

        for i, num in enumerate(nums):
            current_sum += num  # 计算当前累积和

            # 检查是否存在一个之前的累积和等于current_sum - k
            if current_sum - k in cumulative_sum:
                max_length = max(max_length, i - cumulative_sum[current_sum - k])

            # 如果当前累积和不在哈希表中，则将其加入
            if current_sum not in cumulative_sum:
                cumulative_sum[current_sum] = i

        return max_length

Explain

这个题解使用前缀和和哈希表的方法来解决问题。通过维护一个哈希表，记录每个前缀和出现的最早下标，然后在遍历数组的过程中，检查当前前缀和减去目标值 k 是否在哈希表中出现过。如果出现过，则更新最长子数组的长度。这样可以在遍历一次数组的过程中，找到和等于 k 的最长子数组的长度。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        # 初始化哈希表，用于记录累积和及其对应的下标
        cumulative_sum = {0: -1}  # 累积和为0的下标是-1，用于处理从数组起始位置开始的子数组
        max_length = 0  # 最长连续子数组长度
        current_sum = 0  # 当前累积和

        for i, num in enumerate(nums):
            current_sum += num  # 计算当前累积和

            # 检查是否存在一个之前的累积和等于current_sum - k
            if current_sum - k in cumulative_sum:
                # 如果存在，更新最长子数组的长度
                max_length = max(max_length, i - cumulative_sum[current_sum - k])

            # 如果当前累积和不在哈希表中，则将其加入
            if current_sum not in cumulative_sum:
                cumulative_sum[current_sum] = i

        return max_length

Explore

初始化累积和0对应的下标为-1是为了处理从数组起始位置开始计算的子数组。如果从数组的第一个元素开始到某个位置i的累积和恰好为k，那么根据我们的哈希表查询逻辑（current_sum - k），这时current_sum为k，k - k为0。如果哈希表中0的下标是-1，那么 i - (-1) = i + 1，正好等于子数组的长度。因此，这种初始化方法能正确处理包括数组第一个元素在内的子数组情况，使得算法逻辑统一和完整。

只考虑累积和等于`current_sum - k`的情况是因为我们希望找到一段前面的子数组，使得从那个子数组的结束位置到当前位置的子数组之和等于k。具体来说，如果当前的累积和是current_sum，我们需要这个子数组结束的位置的累积和为current_sum - k，这样两者之差就是k，即这段子数组的和就是k。这种方法确实可以覆盖所有可能的和为k的子数组，因为它基于前缀和的性质考虑了从任意位置开始到当前位置的所有子数组情况。

保持累积和最早出现的下标不更新有助于我们找到最长的满足条件的子数组。这是因为当我们在哈希表中查找到一个累积和等于`current_sum - k`时，我们希望这个子数组尽可能长，这就需要这个累积和尽早出现。如果我们更新了累积和的下标为更晚的位置，那么计算得到的子数组长度将会变短，这不利于我们求解最长子数组的问题。因此，保持最早的下标可以确保每次计算的子数组都是以最早的累积和为基准，从而可能得到更长的子数组长度。