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

难度:

标签:

题目描述

代码结果

运行时间: 99 ms, 内存: 57.9 MB

/*
 * 题目思路:
 * 1. 我们需要找到和等于 k 的最长子数组长度。
 * 2. 使用一个哈希图来存储当前前缀和和它对应的索引。
 * 3. 使用流处理数组，计算当前的前缀和。
 * 4. 使用Optional和map处理逻辑。
 */
 
import java.util.HashMap;
import java.util.Optional;
import java.util.stream.IntStream;
 
public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
        final int[] maxLen = {0};
        final int[] prefixSum = {0};
 
        IntStream.range(0, nums.length).forEach(i -> {
            prefixSum[0] += nums[i];
 
            if (prefixSum[0] == k) {
                maxLen[0] = i + 1;
            }
 
            Optional.ofNullable(prefixSumMap.get(prefixSum[0] - k)).ifPresent(index -> {
                maxLen[0] = Math.max(maxLen[0], i - index);
            });
 
            prefixSumMap.putIfAbsent(prefixSum[0], i);
        });
 
        return maxLen[0];
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在哈希表中初始存入累积和0对应的下标-1？这样的初始化有什么特殊意义吗？

▷

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

🦆

如果当前累积和已经在哈希表中存在，为什么不更新其对应的下标？保持最早出现的下标有什么优势？

▷

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

相关问题

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= i <= j < nums.length
最多调用 10⁴ 次 sumRange 方法

连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

1 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1

乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0

提示:

1 <= nums.length <= 3 * 10⁴
1 <= nums[i] <= 1000
0 <= k <= 10⁶

摆动排序 II 区间和的个数