算法沉淀——前缀和（leetcode真题剖析）

算法沉淀——前缀和

• 01.一维前缀和
• 02.二维前缀和
• 03.寻找数组的中心下标
• 04.除自身以外数组的乘积
• 05.和为 K 的子数组
• 06.和可被 K 整除的子数组
• 07.连续数组
• 08.矩阵区域和

  前缀和算法是一种用于高效计算数组或序列中某个范围内元素之和的技巧。它通过预先计算数组的前缀和，并将这些前缀和保存在辅助数组中，从而在查询某个区间的和时能够以常数时间复杂度进行计算。

  

  在实际应用中，前缀和算法经常用于解决与区间和相关的问题，例如子数组和的最大值、最小值、等于目标值的个数等。前缀和的应用能够优化问题的时间复杂度，提高算法的效率。

  01.一维前缀和

  题目链接：https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

  描述

  给定一个长度为n的数组a1,a2,....an.

  接下来有q次查询, 每次查询有两个参数l, r.

  对于每个询问, 请输出al+al+1+....+ar

  输入描述：

  第一行包含两个整数n和q.

  第二行包含n个整数, 表示a1,a2,....an.

  接下来q行,每行包含两个整数 l和r.

  输出描述：

  输出q行,每行代表一次查询的结果.

  示例1

  输入：

  3 2
  1 2 4
  1 2
  2 3
  

  输出：

  3
  6
  

  思路

  1. 通过数组 arr 存储输入的 n 个整数，数组 dp 存储数组 arr 的前缀和。
  2. 使用循环读取数组元素，并计算前缀和 dp。
  3. 进行 q 次查询，每次查询给定一个区间 [l, r]。查询结果为 dp[r] - dp[l-1]，表示数组在区间 [l, r] 的和。
  4. 输出每次查询的结果。

  代码

  #include 
  using namespace std;
  int main() {
      int n,q;
      cin>>n>>q;
      long long arr[100001]={0},dp[100001]={0};
      for(int i=1;i
          cin>arr[i];
          dp[i]=arr[i]+dp[i-1];
      }
      while(q--){
          int l,r;
          cin>>l>>r;
          cout
      cinnm>>q;
      for(int i=1;i
          for(int j=1;j
              cinarr[i][j];
              dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];
          }
      }
      
      while(q--){
          cin>>x1>>y1>>x2>>y2;
          cout
  public:
      int pivotIndex(vector
          int n=nums.size();
          vector
              l[i]=l[i-1]+nums[i-1];
              r[j]=r[j+1]+nums[j+1];
          }
          for(int i=0;i
  public:
      vector
          int n=nums.size();
          vector
              lm[i]=lm[i-1]*nums[i-1];
              rm[j]=rm[j+1]*nums[j+1];
          }
          for(int i=0;i
  public:
      int subarraySum(vector
          unordered_map
              sum+=x;
              if(hash.count(sum-k)) ret+=hash[sum-k];
              hash[sum]++;
          }
          return ret;
      }
  };
  
  public:
      int subarraysDivByK(vector
          unordered_map
              sum+=x;
              int r=(sum%k+k)%k;
              if(hash.count(r)) ret+=hash[r];
              hash[r]++;
          }
          return ret;
      }
  };
  
  public:
      int findMaxLength(vector
          unordered_map
              sum+=nums[i]==0?-1:1;
              if(hash.count(sum)) ret=max(ret,i-hash[sum]);
              else hash[sum]=i;
          }
          return ret;
      }   
  };
  
  public:
      vector
          int m=mat.size(),n=mat[0].size();
          vector
              for(int j=0;j
                  int x1=max(0,i-k)+1,y1=max(0,j-k)+1;
                  int x2=min(m-1,i+k)+1,y2=min(n-1,j+k)+1;
                  ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
              }
          }
          return ret;
      }
  };