LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.27
• 题目：3381.长度可被 K 整除的子数组的最大元素和
• 难度：中等
• 标签：数组、前缀和、哈希表、数学

1. 题目理解

问题描述：
给定一个整数数组 nums 和一个整数 k，请找出数组中长度能被 k 整除的非空子数组的最大和。如果不存在这样的子数组，返回符合条件的最大和（题目保证至少存在一个有效子数组）。

示例：

示例 1：
输入：nums = [3,1,2,4], k = 3
输出：7
解释：长度能被3整除的子数组有 [3,1,2]（和为6）、[1,2,4]（和为7），最大和为7。

示例 2：
输入：nums = [1,2], k = 1
输出：3
解释：所有子数组长度都能被1整除，最大和为1+2=3。

示例 3：
输入：nums = [-1,-2,-3], k = 3
输出：-6
解释：唯一长度为3的子数组和为-6。

2. 解题思路

核心观察

• 子数组的和可通过前缀和快速计算：若 prefixSum[i] 表示前 i 个元素的和，则子数组 nums[j..i-1] 的和为 prefixSum[i] - prefixSum[j]。
• 子数组长度 i-j 能被 k 整除的充要条件是：i % k == j % k（即前缀和索引的余数相同）。
• 要最大化子数组和，需对每个余数 r，记录最早出现的最小前缀和（因为 prefixSum[i] - prefixSum[j] 中，prefixSum[j] 越小，差值越大）。

算法步骤

1. 初始化前缀和数组：用 minPrefix[r] 存储余数 r 对应的最小前缀和，初始化为无穷大，minPrefix[0] = 0（前缀和为0时余数为0）。
2. 遍历计算前缀和：累加当前元素得到 prefixSum，计算当前索引的余数 r = (i+1) % k。
3. 更新最大和：若 minPrefix[r] 已存在（非无穷大），则用 prefixSum - minPrefix[r] 更新最大和。
4. 维护最小前缀和：若当前 prefixSum 小于 minPrefix[r]，更新 minPrefix[r] 为当前 prefixSum。

3. 代码实现

import java.util.Arrays;

class lc3600_lc3699.lc3660.Solution {
    public long maxSubarraySum(int[] nums, int k) {
        // minPrefix[r] 存储余数r对应的最小前缀和（初始化为无穷大）
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE);
        minPrefix[0] = 0; // 前缀和为0时，余数0对应的最小前缀和是0
        
        long prefixSum = 0; // 当前前缀和
        long maxSum = Long.MIN_VALUE; // 记录最大子数组和
        
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i]; // 更新当前前缀和
            
            // 计算当前前缀和对应的索引(i+1)的余数r（子数组长度 = i+1 - j）
            int r = (i + 1) % k;
            
            // 如果余数r已存在最小前缀和，说明存在子数组长度可被k整除
            if (minPrefix[r] != Long.MAX_VALUE) {
                maxSum = Math.max(maxSum, prefixSum - minPrefix[r]);
            }
            
            // 更新余数r对应的最小前缀和（保留更小的前缀和，以便后续得到更大的差值）
            if (prefixSum < minPrefix[r]) {
                minPrefix[r] = prefixSum;
            }
        }
        
        return maxSum;
    }
}

4. 代码优化说明

• 空间优化：用数组替代哈希表存储余数对应的最小前缀和，时间复杂度从 O(n) 优化为更高效的数组访问（哈希表存在哈希冲突风险）。
• 初始化优化：直接用 Long.MAX_VALUE 标记未访问的余数，避免额外的哈希表判空操作。
• 提前终止：题目保证存在有效子数组，无需处理无结果的情况；若需兼容无效情况，可最后判断 maxSum 是否为初始值并返回 -1。

5. 复杂度分析

• 时间复杂度：O(n)，仅遍历数组一次，每次操作均为 O(1)。
• 空间复杂度：O(k)，需维护长度为 k 的 minPrefix 数组，空间开销与 k 成正比（k 远小于 n 时更高效）。

6. 总结

• 本题核心是前缀和 + 余数配对，利用数学性质将“长度可被k整除”转化为“余数相同”，避免暴力枚举所有子数组（暴力法时间复杂度 O(n²)）。
• 关键技巧是记录每个余数的最小前缀和，确保能得到最大的子数组和差值。
• 该思路可推广到“子数组长度满足特定模条件”的同类问题，如“子数组和能被k整除”“子数组长度为k的倍数”等场景。