本文主要是介绍Prefix Sum 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
注意：prefixsum一般都是用PrefixSum[n+1]的数组，prefix[0] = 0; 那么
因为i, j 是A里面的坐标，而prefixsum比A多了1；所以原来的sum[j] - sum[i-1]变成了
sum(i~j) = prefixsum(j + 1) - prefixsum(i);
Interval Sum 思路：因为这个题目不需要modify数组操作，所以用prefix sum array就可以解决，O(N + M) N是数组大小，M是query次数；
/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start = start;* this.end = end;* }* }*/public class Solution {/*** @param A: An integer list* @param queries: An query list* @return: The result list*/public List<Long> intervalSum(int[] A, List<Interval> queries) {List<Long> list = new ArrayList<>();int n = A.length;long[] prefixsum = new long[n + 1];prefixsum[0] = 0;for(int i = 1; i <= n; i++) {prefixsum[i] = prefixsum[i - 1] + A[i - 1];}for(Interval interval: queries) {list.add(prefixsum[interval.end + 1] - prefixsum[interval.start]);}return list;}
}Subarray Sum 用prefixsum, A[i ~ j] = 0; 相当于 S[i-1] == S[j]，也就是在数组里面找相等的数；hashmap, 存 S[i], i 就可以了；一定要存index；注意用hashmap put(0,0)因为是为了如果有sum直接== 0， 那么length应该是i - 0 = i;
public class Solution {/*** @param nums: A list of integers* @return: A list of integers includes the index of the first number and the index of the last number*/public List<Integer> subarraySum(int[] nums) {List<Integer> res = new ArrayList<>();if(nums == null || nums.length == 0) {return res;}int n = nums.length;int[] prefixSum = new int[n + 1];prefixSum[0] = 0;for(int i = 1; i <= n; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i - 1];}HashMap<Integer, Integer> hashmap = new HashMap<>();hashmap.put(0, 0);for(int i = 1; i <= n; i++) {if(hashmap.containsKey(prefixSum[i])) {// -1：prefixsum的index都要-1，才能map到原来的array index上；// +1：A[i...j] == 0 -> sum[j] == sum[i - 1]; 求i, 所以要+1;res.add(hashmap.get(prefixSum[i] - 1 + 1));res.add(i - 1);}hashmap.put(prefixSum[i], i);}return res;}
}Subarray Sum II
思路：固定右边界aj, 问题转换为找左边的两个边界，
XXXVVVVVVVVXXXXX aj
.....ai .................ak ........ aj
<=end >=start
这两个区间都是可以用双指针来计算得到的，O(N)
Prefix Sum 现在用n+1数组来求；
public class Solution {/*** @param A: An integer array* @param start: An integer* @param end: An integer* @return: the number of possible answer*/public int subarraySumII(int[] A, int start, int end) {if(A == null || A.length == 0) {return 0;}int n = A.length;int[] prefixSum = new int[n + 1];prefixSum[0] = 0;for(int i = 1; i <= n; i++) {prefixSum[i] = prefixSum[i - 1] + A[i - 1];}int res = 0;/**XXXXXXVVVVVVVVVXXXXXX j>end <startleft right*/int left = 0, right = 0;for(int j = 1; j <= n; j++) {while(right < j && prefixSum[j] - prefixSum[right] >= start) {right++;}while(left < j && prefixSum[j] - prefixSum[left] > end) {left++;}res += (right - left);}return res;}
}Subarray Sum Closest 思路：将prefixsum的array，排序，然后比较相邻的两个sum，如果求diff最小的，注意；如果prefixsum == 0，则不用找了，找了个最佳答案，否则看最相近的；
public class Solution {/** @param nums: A list of integers* @return: A list of integers includes the index of the first number and the index of the last number*/private class Node {public int index;public int sum;public Node(int index, int sum) {this.index = index;this.sum = sum;}}public int[] subarraySumClosest(int[] nums) {int[] res = new int[2];if(nums == null || nums.length == 0) {return res;}int n = nums.length;int[] sum = new int[n + 1];sum[0] = 0;List<Node> list = new ArrayList<Node>();for(int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + nums[i - 1];if(sum[i] == 0) {res[0] = 0;res[1] = i - 1;return res;}list.add(new Node(i, sum[i]));}Collections.sort(list, (a, b) ->(a.sum - b.sum));int diff = Integer.MAX_VALUE;for(int i = 0; i < list.size() - 1; i++) {int curdiff = list.get(i + 1).sum - list.get(i).sum;if(curdiff < diff) {diff = curdiff;// sum[i, j] = S[j] - S[i - 1], 所以真正的区间是: [i + 1, j]if(list.get(i).index < list.get(i + 1).index) {res[0] = list.get(i).index;res[1] = list.get(i + 1).index - 1;} else {res[0] = list.get(i + 1).index;res[1] = list.get(i).index - 1;}}}return res;}
}Submatrix Sum 用prefixsum，代表是从(0,0) 到(i,j) 的区域sum。然后固定上边界和下边界，然后扫描j，用hashmap来找有没有重复的区域，如果有就找到了区域为0的，然后记录答案，注意，因为prefixsum是+1了的index，所以，最后右下角的点需要减去1，左上角的点因为默认+1，所以不用减去1了。 O(N^3); Space O(N^2);
public class Solution {/** @param matrix: an integer matrix* @return: the coordinate of the left-up and ri这篇关于Prefix Sum 总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
