【算法】——前缀和

 

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

目录

一：前缀和模版

二：前缀和模版2

三：寻找数组的中心下标

四：除自身以外数组的乘积

五：和为K的子数组

六：和被k整除的子数组

七：连续数组

八：矩阵区域和

一：前缀和模版

【模板】前缀和_牛客题霸_牛客网

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //1：获取输入
        int n = in.nextInt() , q = in.nextInt();//长度为n的数组，q次查询
        int[] arr = new int[n+1];
        for(int i = 1 ; i <= n ; i++){
            arr[i] = in.nextInt();
        }

        //2：创建dp数组
        long[] dp = new long[n+1]; 
        for(int i = 1 ; i <= n ; i++){
            dp[i] = dp[i-1] + arr[i];
        }

        while(q > 0){
            int l = in.nextInt() , r = in.nextInt();
            System.out.println(dp[r]-dp[l-1]);
            q--;
        }

         
    }
}

二：前缀和模版2

【模板】二维前缀和_牛客题霸_牛客网

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
       int n = in.nextInt() , m = in.nextInt() , q = in.nextInt();
        
        //arr数组
       long[][] arr = new long[n+1][m+1];
       for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            arr[i][j] = in.nextInt();
        }
       }

       //copy创建一个dp数组

       long[][] dp = new long[n+1][m+1];
       for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
        }
       }

       while(q > 0){
        int x1 = in.nextInt() , y1 = in.nextInt() , x2 = in.nextInt() , y2 = in.nextInt();
        long result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
        System.out.println(result);
        q--;
       }
    }
}

三：寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        //前缀和数组
        int[] f = new int[n];
        f[0] = 0;
        for(int i = 1 ; i < n ; i++){
            f[i] = f[i-1] + nums[i-1];
        }   
        //后缀和数组
        int[] g = new int[n];
        g[n-1] = 0;
        for(int i = n-2 ; i >= 0 ; i--){
            g[i] = g[i+1] + nums[i+1];
        }
        int result = Integer.MAX_VALUE;
        for(int i = 0 ; i < n ; i++){
            if(f[i] == g[i]){
                result = Math.min(result,i);
            }
        }
        if(result == Integer.MAX_VALUE){
            return -1;
        }else{
            return result;
        }

    }
}

四：除自身以外数组的乘积

 238. 除自身以外数组的乘积 - 力扣（LeetCode）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        //前缀积
        int[] f = new int[n];
        f[0] = 1;
        for(int i=1 ; i<n ; i++ ){
            f[i] = f[i-1]*nums[i-1];
        }

        int[] g = new int[n];
        g[n-1] = 1;
        for(int i=n-2 ; i >= 0 ; i--){
            g[i] = g[i+1]*nums[i+1];
        }

        int[] answer = new int[n];
        for(int i = 0 ; i < n ; i++){
            answer[i] = f[i]*g[i];
        }
        return answer;
    }
}

五：和为K的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        int sum = 0 , ret = 0;
        for(int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum-k,0);
            hash.put(sum,hash.getOrDefault(sum,0)+1);
        }
        return ret;
        
    }
}

六：和被k整除的子数组

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); 
        hashMap.put(0 % k , 1);//默认有一个前缀和=0

        int sum = 0;//前缀和
        int ret = 0;//用来计数
        for(int x : nums){
            sum += x;
            int remainder = (sum % k + k) % k;
            ret += hashMap.getOrDefault(remainder,0);
            hashMap.put(remainder,hashMap.getOrDefault(remainder,0)+1);
        }

        
        return ret;
    }
}

七：连续数组

525. 连续数组 - 力扣（LeetCode）

class Solution {
    public int findMaxLength(int[] nums) {
        
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i] == 0){
                nums[i] = -1;
            }
        }
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,-1);
        int sum = 0 , ret = 0;
        for(int i = 0 ; i < nums.length ; i++){
            sum += nums[i];
            if(hash.containsKey(sum)){
                int old = hash.get(sum);
                int tem = i-old;
                ret = Math.max(ret,tem);
            }else{
                hash.put(sum,i);
            }

        }
        return ret;
    }
}

八：矩阵区域和

1314. 矩阵区域和 - 力扣（LeetCode）

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length , n = mat[0].length;

        //1：初始化dp前缀和数组
        int[][] dp = new int[m+1][n+1];
        for(int i = 1 ; i < m+1 ; i++){
            for(int j = 1 ; j < n+1 ; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        //2:处理前缀和数组
        int[][] ret = new int[m][n];
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                int x1 = Math.max(0,i-k)+1 , y1 = Math.max(0,j-k)+1;
                int x2 = Math.min(i+k,m-1)+1 , y2 = Math.min(j+k,n-1)+1;
                ret[i][j] = dp[x2][y2] - dp[x2][y1-1] -dp[x1-1][y2] + dp[x1-1][y1-1];
            }
        }
        return ret;
    



    }
}