算法笔记-前缀和/差分

必备知识

前缀和

定义：对前面的数进行求和作为当前项

一维前缀和：

有一个一维数组 和该数组的一维前缀和数组 ，则 和 满足以下关系：

二维前缀和：

有一个二维数组 和该数组的二维前缀和数组 （其同样是个二维数组），则 和 满足以下关系：

差分

定义：当前项减去前一项，d[i] = a[i]-a[i-1] ，差分数组是当前数组项减去数组前一项得出组成新数组。

性质：差分数组求前缀和结果等于原数组

用途：基于差分数组的性质，差分数组最主要用于对数组部分区间进行同时加上或减去一个数。如需要在区间[l,r]同时加上5，只需要在d[l]=d[l]+5，d[r]=d[r]-5即可

案例：

原数组	1	3	3	4	2	6	7
前缀和	1	4	7	11	13	19	26
差分	1	（3-1）= 2	（3-3）= 0	（4-3）= 1	（2-4）= -2	（6-2）= 4	（7-6）= 1

两者关系

对差分数组求前缀和，可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组

相关题目

前缀和相关题目

525 连续数组
526 连续的子数组和
527 元素和为目标值的子矩阵数量
528 和为k的子数组
529 每个元音包含最长的子字符串
530 统计「优美子数组」 LCP 19：秋叶收藏集
531 矩形区域不超过 K 的最大数值和

连续数组

class Solution {
    //前缀和:使用map存储
    //arr     =    [ 0,1,1,1,0,0,1,0,1]
    //prefix-sum = [-1,0,1,2,1,0,1,0,1]
    //index   =    [ 0,1,2,3,4,5,6,7,8]
    public int findMaxLength(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int counter = 0;//记录前缀和
        map.put(counter, -1);//初始值
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {//遇到1++
                counter++;
            } else {//遇到0--
                counter--;
            }
            //当counter == 上次出现counter值,下标为[i,j],说明当前区间[i,j]的0和1正好相互抵消了，所以个数=j-i
            if (map.containsKey(counter)) {
                int prevIndex = map.get(counter);
                maxLength = Math.max(maxLength, i - prevIndex);
            } else {
                map.put(counter, i);
            }
        }
        return maxLength;
    }
}

2100. 适合打劫银行的日子

class Solution {
    //前缀和,left记录从左向右递减个数，right记录从右向左递增的个数，在判断是否左右满足
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        int[] left = new int[n];
        int[] right = new int[n];
        //记录左右
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
            if (security[n - i - 1] <= security[n - i]) {
                right[n - i - 1] = right[n - i] + 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        //判断是否满足time
        for (int i = time; i < n - time; i++) {
            if (left[i] >= time && right[i] >= time) {
                ans.add(i);    
            }
        }
        return ans;
    }
}

2055. 蜡烛之间的盘子

class Solution {
    //思路：前缀和
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int m = queries.length;
        int[] ret = new int[m];
        int[] left = new int[n];
        int[] right = new int[n];
        int[] preSum = new int[n];
        
        //当前i离左边蜡烛最近距离
        for(int i=0,leftIndex = -1;i<n;i++){
            char c = s.charAt(i);
            if(c=='|')leftIndex = i;
            left[i] = leftIndex;
        }
        //当前i离右边蜡烛最近距离
        for(int i=n-1,rightIndex = -1;i>=0;i--){
            char c = s.charAt(i);
            if(c=='|')rightIndex = i;
            right[i] = rightIndex;
        }
        //盘子的前缀和
        for(int i=0,sum=0;i<n;i++){
            if(s.charAt(i)=='*')sum++;
            preSum[i]=sum;
        }
        //计算每个区间
        for(int i=0;i<m;i++){
            int[] arr = queries[i];
            int l = arr[0],r = arr[1];
            //left[r]==-1 表示从0左区间到右区间r没有蜡烛
            //right[l]==-1 表示从n-1右区间到左区间l没有蜡烛
            //left[r]<=right[l] 
            //因为记录的是下标，所以
            //left[r]表示从0-r到r中最靠近r的蜡烛位置（其实就是我们要求的右区间）
            //right[l]表示从n-1到l最靠近l的蜡烛位置（其实就是我们要求的左区间）
            if(left[r]==-1||right[l]==-1||left[r]<=right[l])ret[i]=0;
            //所以个数就是右区间减去左区间的值
            else ret[i]=preSum[left[r]]-preSum[right[l]];
        }
        return ret;
    }
}

差分相关题目

731. 我的日程安排表 II（mid）

相关资料