前綴和
- 前綴和
- 二維前綴和
- 尋找數組的中心下標
- 除自身以外數組的乘積
- 和為k的子數組
- 和可被K整除的子數組
- 連續數組
- 矩陣區域和
前綴和
題目解析：在一個數組中查詢起對應區間的和，會查詢多次
算法思想：暴力解法：每次查詢都進行一次遍歷，時間複雜度O(n*m)
前綴和解法：新定義一個數組，每一個下標存放的值是要查詢數組的前下標對應值的和，這樣我們在訪問起某一個區間的時候，直接利用這個數組就非常快速
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 m = in.nextInt();
int[] arr = new int[n+1];//此時我們讓其下標從1開始，這樣可以省略邊界問題考慮
arr[0] = 0;
for(int i = 1;i <= n;i++){
arr[i] = in.nextInt();
}
//題目意思就是給了我們長度是n的數組，但是會有m查詢
//1.首先定義一個新的數組，其每一個下標對應的值是其從arr1開始到這個下標值的和
long[] dp = new long[n+1];
for(int i = 1;i <= n;i++){
dp[i] = dp[i - 1] + arr[i];
}
while(m > 0){
int l = in.nextInt();
int r = in.nextInt();
System.out.println(dp[r] - dp[l - 1]);
m--;
}
}
}時間複雜度：O(n + m)
空間複雜度：O(n)
二維前綴和
題目解析：和上一題一樣，只不過這裏變成了二維數組，要求的是對應子矩陣元素之和
前綴和：先定義一個新數組dp，其下標對應的值是原arr 數組[1,1] ~ [i, j]下標的和，此時還是讓其下標從1開始這樣就不用考慮下標越界情況
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();
int m = in.nextInt();
int q = in.nextInt();
//下標從1開始
int[][] arr = new int[n+1][m+1];
for(int i = 1;i <= n;i++){
for(int j = 1;j<=m;j++){
arr[i][j] = in.nextInt();
}
}
//前綴和數組
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] + arr[i][j] - dp[i-1][j-1];
}
}
//使用前綴和數組
while(q > 0){
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
System.out.println(dp[x2][y2] -dp[x1-1][y2]-dp[x2][y1-1] + dp[x1-1][y1-1]);
q--;
}
}
}時間複雜度：O(n*m + q)
空間複雜度：O(n * m)
尋找數組的中心下標
題目解析：找到一個下標，讓其數組左邊元素的和等於其右邊元素的和
前綴和算法：由於暴力解法每次都要進行遍歷多次，這樣時間複雜度高
因此我們可以使用f和g兩個數組，一個每一個下標用來放其前綴和，一個用來放後綴和，最後遍歷一遍判斷其f[i] == g[i]即可
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
//此時f要從左向右填寫，因為後一個要根據前一個填寫
for(int i = 1;i < n;i++){
f[i] = f[i-1] + nums[i-1];
}
for(int i = n-2;i >= 0;i--){
g[i] = g[i+1] + nums[i+1];
}
for(int i = 0;i< n;i++){
if(f[i] == g[i]){
return i;
}
}
return -1;
}
}時間複雜度：O(n)
空間複雜度：O(n)
除自身以外數組的乘積
題目解析：返回一個answer數組，裏面answer[i]表示的是nums數組中除了num[i]下標的值，其他所有元素的積，返回這個answer數組
前綴積：f表示前綴積，g表示後綴積
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
//一個前綴積和一個後綴積
int[] f = new int[n];
int[] g = new int[n];
int[] ret = new int[n];
f[0] = g[n-1] = 1;
for(int i = 1;i < n;i++){
f[i] = f[i-1] * nums[i-1];
}
for(int i = n - 2;i >= 0;i--){
g[i] = g[i+1] * nums[i+1];
}
for(int i = 0 ; i<n;i++){
ret[i] = f[i]*g[i];
}
return ret;
}
}和為k的子數組
題目解析：數組中找子數組和為k的個數
前綴和：有一個前綴和數組，這樣每次我們只要在[ 0 , i-1]找出和為nums[i] - k即可,
但是如果sum[i] == k，此時就要從 [0,-1]中找0，因此可以先將<0,1>放入hash中
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> hash = new HashMap<>();
hash.put(0,1);
int sum = 0;//表示前綴和
int ret = 0;
for(int num : nums){
sum += num;
ret += hash.getOrDefault(sum - k, 0);//更新結果
hash.put(sum,hash.getOrDefault(sum,0)+1);//將其放入hash中
}
return ret;
}
}時間複雜度：O(n)
空間複雜度：O(n)
和可被K整除的子數組
題目解析：在一個數組中找出所有子數組和可以整除k的子數組個數
這個題目和上一個求所有和為子數組的個數一樣，一些細節處理方式都差不多，唯一不一樣的是
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer,Integer> hash = new HashMap<>();
//剛開始要先將0%k放入進去，也就是<0,1>,防止當
hash.put(0 % k,1);
int sum = 0;
int ret = 0;
for(int num : nums){
sum += num;
int r = (sum % k + k)%k;
ret += hash.getOrDefault( r, 0);
hash.put(r,hash.getOrDefault(r,0)+1);
}
return ret;
}
}時間複雜度：O(n)
空間複雜度：O(n)
連續數組
題目解析：找一個最長的子數組其和為0，並且此子數組區間中0和1的個數一樣
題目轉換，我們可以將其中的0看成-1，此時就變成了找出和為0的最長子數組，上面有一個題目是和為k的子數組，此時的k == 0
前綴和 + 哈希表
但是有很多細節不一樣，
1.這裏哈希表存放的是<前綴和,下標>
2.重複的哈希其不用存放，因為這裏要求的是最長子數組
3.長度為i - j
4.<0,-1>,前綴和為0，存放的是-1
5.先使用，後存放入哈希表中
class Solution {
public int findMaxLength(int[] nums) {
//此時可以將其0看成-1，此時就變成和為0的最長子數組的求解
Map<Integer,Integer> hash = new HashMap<>();
//當其[0,i]位置和為0時候，我們要從[0,-1]中找出和為0
hash.put(0,-1);
int len = 0;
int sum = 0;
for(int i = 0;i < nums.length ;i++){
if(nums[i] == 0){
sum -= 1;
}else{
sum += 1;
}
//從前面找和為sum，那後面和就為0，當然其j越靠前越好
//因此如果已經有了和為sum，後面的就不用放進去了
if(hash.containsKey(sum)){
len = Math.max(len,i - hash.get(sum));
}else{
//放入hash中
hash.put(sum,i);
}
}
return len;
}
}時間複雜度：O(n)
空間複雜度：O(n)
矩陣區域和
題目解析：給了一個二維數組，我們要返回一個相同的二維數組，每一個下標對應的值是其原本二維數組距離其為k的元素所圍成的一個矩形中元素之和
前綴和矩陣，上面有一個題目是求(x1,y1) 到 (x2,y2)所圍成矩陣的和就用到了前綴和矩陣
因此這裏可以先求出前綴和數組，在使用的時候直接根據k求出其是那兩個座標 圍成的矩形，有了座標可以使用前綴和矩陣，這樣就求出對應的值了
但是此時要注意其下標是不一樣的，前綴和矩陣下標是從1開始
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] dp = new int[m+1][n+1];
//構建前綴和其下標從1開始
for(int i = 1;i<= m;i++){
for(int j = 1;j<= n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
}
}
int[][] ret = new int[m][n];
//使用的時候下標也要+1這樣才能正常使用前綴和數組
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
int x1 = Math.max(i-k,0) + 1;
int y1 = Math.max(j-k,0) + 1;
int x2 = Math.min(i+k, m -1) + 1;
int y2 = Math.min(j+k, n - 1) + 1;
ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
}
}
return ret;
}
}時間複雜度：O(m * n)
空間複雜度：O(m * n)
