子数组问题（最大子数组 · 子数组和为K · 最长连续序列）

最大子数组（LeetCode 53）

Kadane 算法：局部最优推全局最优。

int maxSubArray(int[] nums) {
    int maxSum = nums[0], curSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]);  // 要么接上，要么重新开始
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

DP 定义：dp[i] = 以 nums[i] 结尾的最大子数组之和。

• dp[i] = max(nums[i], dp[i-1] + nums[i])

分治解法（O(n log n)，了解即可）：

• 递归分左右，跨越中点部分单独计算

子数组和为 K（LeetCode 560）

前缀和 + 哈希表，O(n)：

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // 空前缀
    int count = 0, sum = 0;
    for (int n : nums) {
        sum += n;
        // 若 sum-k 在表中，说明存在以该位置结尾、和为k的子数组
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

变体：最长子数组和为 k（需要存最早出现的前缀和位置）：

int maxSubArrayLen(int[] nums, int k) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1);
    int maxLen = 0, sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (firstIndex.containsKey(sum - k))
            maxLen = Math.max(maxLen, i - firstIndex.get(sum - k));
        firstIndex.putIfAbsent(sum, i);  // 只存第一次出现
    }
    return maxLen;
}

乘积最大子数组（LeetCode 152）

因为负数 × 负数 = 正，需同时维护 最大值和最小值：

int maxProduct(int[] nums) {
    int maxProd = nums[0], minProd = nums[0], res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        int tempMax = Math.max(n, Math.max(maxProd * n, minProd * n));
        int tempMin = Math.min(n, Math.min(maxProd * n, minProd * n));
        maxProd = tempMax;
        minProd = tempMin;
        res = Math.max(res, maxProd);
    }
    return res;
}

最长连续序列（LeetCode 128）

要求 O(n)，用 HashSet：

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int longest = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {  // 只从序列起点开始
            int cur = n, len = 1;
            while (set.contains(++cur)) len++;
            longest = Math.max(longest, len);
        }
    }
    return longest;
}

总结对比