前缀和算法：提升编程效率的秘密武器(Java版)

邂逅岁月

已于 2024-05-26 09:56:43 修改

阅读量1.3k

点赞数 133

分类专栏：题海寻offer “掌掴”算法之路数据结构的九曲回肠文章标签：算法面试刷题前缀和

于 2024-05-26 09:54:27 首次发布

本文链接：https://blog.csdn.net/mgzdwm/article/details/139022333

版权

本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！

在这里插入图片描述

前言

在前面我们熟悉了 == “双指针” 算法== ，== “滑动窗口” 算法==，以及 二分查找 算法。小伙伴可以思考下，

这些本质上是不是都是双指针呢，没错，当然是的 💖 💖 💖

这三个专题我们已经 圆满结束啦, 那么我们的双指针大家族也算是告一段落啦 💖 💖 💖

而在本篇我们中讲新的专题，是去双指针不同的专题， 前缀和 算法

下面小伙伴先了解下本篇文章的规划吧 😊 😊 😊

一. 前缀和算法的初识

<1>. 前缀和算法的简介

前缀和算法，也称为 前缀和技巧 ，是一种常见的算法技巧，用于高效地计算数组或序列中某个 位置前 的 所有元素的和。

前缀和算法的思路是先计算出从数组的起始位置到每个位置的 子数组和 ，然后根据需要的范围计算出相应的结果。

<2>. 前缀和使用流程

我们通过一个简单的题目来讲解前缀和的具体使用吧 💖 💖 💖 💖

1. 前缀和

DP34.前缀和题目链接

<1>. 题目描述

在这里插入图片描述

题目含义：

先 初始化一个数组，并 指定长度，然后在指定一段需要求的 子数组的区间 的总和，进行返回，注意这里要指定 q 次, 意味着我们要求 q 次子数组的总和并返回

<2>. 讲解算法思想

题目分析 ：

遇到求某段区间的总和，我们不难想到

解法一 :

暴力求解

用一个 for 循环来累加左右区间的，然后循环往复进步 q 次

前缀和算法 :

我们先定义一个 数组dp，这个数组是主要用来统计 i 位置到 0 的元素的总和

算法步骤

在这里插入图片描述

第一步：先定义 dp 数组， i = 0 时，先把第一个元素进行 相加，然后到 i = 1 时，我们就在 dp[0] 的基础上加上原数组(假设原数组名为 nums ) nums[1] 那个元素 , 循环往复，意味着就可以得到我们的 每个位置到 0 位置的总和的数据。

在这里插入图片描述

第二步：使用前缀和数组，我们要得到某得区间的，就可以利用前缀和数组，用 dp[右边界] - dp[左边界-1] 就可以得到我们的该区间的和

请添加图片描述

<3>. 编写代码

import java.util.Scanner;




// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   

    public static void main(String[] args) {
   
        
        
        Scanner in = new Scanner(System.in);
        
        
        int n=in.nextInt();
        int q=in.nextInt();
       

       long [] array=new long [n+1];
       for(int i =1 ; i < n+1 ; ++i) {
   
            
            array[i]=in.nextInt();      
       
       }

        int k=0;
        
        long[] sum=new long[q];
        long[] dp=new long[n+1];
        dp[0]=0;
        for(int x= 1; x < n+1 ; x++ ) {
   
            dp[x]= dp[x-1] + array[x];
        }
       
       while(q != 0) {
   
            
            int left = in.nextInt();
            
            int right = in.nextInt();
             
                
                System.out.println(dp[right]-dp[left-1]);                
             

            k++;
            
            q--;
       
       }



   

    }


}