前缀和与差分数组

前缀和问题

示例：对于一个给定的数组，寻找和为k的连续子数组。

思路实现：

对每个元素构建一个前缀和数组，然后遍历该数组所有可能的子数组判断和是否为k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class PrefixSum {
    public List<List<Integer>> subArray(int[] nums,int k){
        //构建前缀和数组sum，长度为nums长度加1
        int n=nums.length;
        int[] sum=new int[n+1];
        sum[0]=0;
        for(int i=0;i<n;i++){
            sum[i+1]=sum[i]+nums[i];
        }
        List<List<Integer>> res=new ArrayList<>();
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(sum[i]-sum[j]==k){
                    List<Integer> str=new ArrayList<>();
                    for(int s=j;s<i;s++){
                        str.add(nums[s]);
                    }
                    res.add(str);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums={-1,3,2,6,4,-2};
        int k=2;
        PrefixSum prefixSum=new PrefixSum();
        List<List<Integer>> result=prefixSum.subArray(nums,k);
        for(List<Integer> c:result){
            System.out.println(c);
        }
    }
}

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

示例：

比如说，我给你输入一个数组nums，然后又要求给区间nums[2..6]全部加 1，再给nums[3..9]全部减 3，再给nums[0..4]全部加 2，再给…，然后问你，最后nums数组的值是什么？

思路分析

构建差分数组。

1
2
3
4
5
6
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}