前缀和总结

前缀和是一个常用的算法技巧，通常用于求解数组或序列的区间和。

具体来说，假设有一个长度为n的数组a，我们可以预处理出一个长度为n+1的前缀和数组s，其中s[i]表示原数组a前i个元素的和，即：

s[i] = a[0] + a[1] + ... + a[i-1]

这样一来，对于任意的区间[l, r]，我们可以通过以下公式计算其和：

sum[l, r] = s[r+1] - s[l]

也就是说，sum[l, r]等于前缀和数组中r+1的值减去前缀和数组中l的值。这个公式的思想是，先计算区间右端点之前的所有元素的和s[r]，再减去区间左端点之前的所有元素的和s[l-1]，这样就可以得到区间[l, r]的和。

通过预处理前缀和数组，我们可以在O(1)的时间复杂度内计算任意区间的和，这在某些问题中非常有用，例如区间最大子段和问题、区间和的最大值/最小值等

实现

        int[] preSum = new int[len + 1];​       for (int l = 0; l < len; l++) for (int r = l; r < len; r++) // 区间和 [l, r]，注意下标偏移if (preSum[r + 1] - preSum[l] == k) { // 前缀和为k//}

上面将前缀和存储在一个数组中，如果需要去重，可以使用哈希表进行存储