当前位置:   article > 正文

【Java数据结构与算法】前缀和算法及相关题解_前缀和算法题

前缀和算法题

一维前缀和

即:
s[1]=a[1]
s[2]=a[1]+a[2]
s[3]=a[1]+a[2]+a[3]
s[4]=a[1]+a[2]+a[3]+a[4]
s[5]=a[1]+a[2]+a[3]+a[4]+a[5]

通过前缀和,我们很容易获取到数组任意 [l ,r]的连续区间的和。后面的前缀和减前面的就是一段连续子数组[l ,r]区间和。

例题:力扣.剑指 Offer II 010. 和为 k 的子数组

题目: 给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。


思路: 如果我们通过暴力枚举所有连续子数组情况,时间复杂度是 O(n^2),
前缀和 + HashMap 可以做到O(n)的时间复杂度

  1. 我们统计前缀和时,当前前缀和为sum,如果当前前缀和恰好为k,或者如果之前统计到过sum - k 的前缀和,
    则说明[0,r]区间和为k,或者当前前缀和减去之前的前缀和,[l,r]区间和恰好是k,
  2. 我们也可以手动添加一个为0的前缀和,以保证通过统计sum - k 便可统计到[0,r]区间及其他区间。
  3. 由于数组有正负值,前缀和可能减少,也可能增大,就可能出现大小重复的前缀和,所有用HashMap保存前缀和及其出现次数.

Java代码:

class Solution {
   public int subarraySum(int[] nums, int k) {
       Map<Integer, Integer> map = new HashMap<>();
       int sum = 0;
       int count = 0;
       map.put(0,1);  //手动添加一个为0的前缀和,以保证统计到[0,r]区间
       for(int i= 0; i < nums.length; i++) {
           sum += nums[i];
           //if(sum == k) count++; //如果没有添加为0的前缀和,就得统计它
           count += map.getOrDefault(sum - k, 0);
           map.put(sum, map.getOrDefault(sum, 0) + 1);
       }
       return count;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

例题:力扣.剑指 Offer II 011. 0 和 1 个数相同的子数组

题目: 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。


思路:和上一题类似前缀和+HashMap 0和1的个数相等,意思就是0的个数减去1的个数等于0。
出现一个0记-1,出现一个1记+1,当前缀和为0时说明[0,r]子数组0和1的个数相等。
当之前的前缀和([0,l])与当前前缀和(0,r)相等时, 说明 [l,r] 子数组中0和1 的个数相同。
用Map记录前缀和及出现的下标,如果前缀和相同则保留最小的下标。
java代码:

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> prefixSums = new HashMap();
        int sum = 0;
        int max = 0;
        prefixSums.put(0,-1); //手动添加一个为0的前缀和,[0,r]区间也可以统计到
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0? -1:1;
            if (prefixSums.containsKey(sum)){
                max = Math.max(max, i - prefixSums.get(sum));
            }else {
                prefixSums.put(sum,i);
            }
        }
        return max;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

例题:力扣.剑指 Offer II 012. 左右两边子数组的和相等

题目:一个整数数组 nums ,请计算数组的 中心下标 。中心下标是数组的一个下标,下标左侧所有元素相加的和等于右侧所有元素相加的和。


思路:
当前位置前一位的前缀和 --> 即当前位置左边连续子数组和,
数组总和-当前位置左边-当前位置 -->即为当前位置右边的连续子数组和,左边==右边 即 中心下标
Java代码:

class Solution {
    public int pivotIndex(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int lastSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // total - lastSum - nums[i] == lastSum
            if(total - 2 * lastSum == nums[i]){
                return i;
            }
            lastSum += nums[i];
        }
        return -1;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

二维前缀和

二维前缀和即二维矩阵,以(0,0)点为左上角, 以当前点为右下角的矩阵和,即 S11= Sum[(0,0),(0,1),(1,0),(1,1)]
图示:
在这里插入图片描述
假设子矩阵左上角位置是 (row1, col1), 右下角位置是(row2, col2),获取子矩阵和:
sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1] + sum[row1][col1]

请添加图片描述

例题:力扣.剑指 Offer II 013. 二维子矩阵的和

题目:计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。

思路: 二维前缀和,为了方便写程序,给前缀和矩阵加上两个为0的边
java代码:

class NumMatrix {
    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

前缀和力扣题目

题目思路
238. 除自身以外数组的乘积左边的乘积先放进去,乘以右边乘积。计算左边、右边乘积过程类似前缀和
303. 区域和检索 - 数组不可变数组保存前缀和,要那一段的和就返回哪一段的和
523. 连续的子数组和map存前缀和的余数与索引, (a - b) % k == 0 即 a % k == b % k,找到余数相同且索引差>1的区间
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/863559
推荐阅读
相关标签
  

闽ICP备14008679号