算法【Java】 —— 前缀和

前缀和（Prefix Sum）是计算数组区间和的一种高效算法，广泛用于处理数组中子区间和的问题。通过预先计算前缀和数组，可以在常数时间复杂度内查询任意子区间的和。本文将详细介绍前缀和的概念及其在Java中的实现，并给出代码示例。

前缀和的定义

给定一个整数数组 nums，我们定义前缀和数组 prefixSum，其第 i 个元素表示数组 nums 从起始位置到 i 的累积和。即：

prefixSum[i] = nums[0] + nums[1] + ... + nums[i]

为了便于计算，我们常常定义 prefixSum[0] 为 0，这样可以减少边界条件的处理。根据上述定义，可以推出 prefixSum[j] - prefixSum[i-1] 即为 nums[i] 到 nums[j-1] 的和。

前缀和的计算过程

1. 初始化一个前缀和数组 prefixSum，长度为 n + 1（其中 n 为原数组 nums 的长度），并将 prefixSum[0] 设为 0。
2. 使用循环遍历原数组 nums，计算前缀和，更新 prefixSum。

在 Java 中实现前缀和

以下是前缀和的 Java 实现示例：

import java.util.Arrays;

public class PrefixSum {
    private int[] prefixSum;

    // 构造函数，初始化前缀和数组
    public PrefixSum(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n + 1]; // 第0个元素为0
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

    // 查询从 left 到 right 的区间和
    public int rangeSum(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        PrefixSum ps = new PrefixSum(nums);

        // 查询不同的区间和
        System.out.println(ps.rangeSum(0, 2)); // 输出: 6 (1 + 2 + 3)
        System.out.println(ps.rangeSum(1, 4)); // 输出: 14 (2 + 3 + 4 + 5)
        System.out.println(ps.rangeSum(0, 4)); // 输出: 15 (1 + 2 + 3 + 4 + 5)
    }
}

代码解释

1. PrefixSum 类：该类用于封装前缀和的实现。构造函数接收一个整数数组 nums，并计算对应的前缀和数组 prefixSum。
2. 构造函数：使用一个循环遍历数组，将每个元素的和逐步累加到 prefixSum 中。
3. rangeSum 方法：接收两个参数 left 和 right，用于查询 nums[left] 到 nums[right] 的和。通过前缀和数组的差值运算，可以实现 O(1) 的时间复杂度查询。
4. main 方法：测试了之前构建的前缀和类，通过输入不同的区间输出相应的和。

总结

前缀和是一种简单而高效的方法，可以在 O(n) 的时间复杂度内预处理数组，使得在 O(1) 的时间复杂度内快速查询区间和，非常适用于需要频繁查询的场景。通过 Java 的实现示例，能够更加清晰地理解前缀和的逻辑及应用。如果在实际工作中经常需要计算区间和，前缀和是一个非常有用的工具。