#关于前缀和解决子数组问题

## 一 前置知识前缀和### 1.1定义对于数组arr 有一个sum数组满足sum[0] 0; sum[i] 是arr前i个数的和对于sum[i] 和sum[i-1] 即 sum[i] 多加了一个arr[i-1] 所以 sum[i] sum[i-1]arr[i-1]### 1.2 前缀和代码实现javapublic static int[] arr,sum; public static int n; public static void getPrefixSum(){ n arr.length; sum new int[n1]; sum[0] 0; for(int i1;in;i){ sum[i] sum[i-1]arr[i-1]; } }### 1.3 应用前缀和数组多次查询区间 L到R位置的和sum[l]是下标0到下表l-1 位置的和 sum[r]同理 因为有sum[0] 0;所以l到r的和为sum[r1]-sum[l]如果题目给的是位置 l , r 用 sum[r] - sum[l-1]###1.4 代码实现javapublic static int getRangePrefixSum(int l,int r) { //return sum[r1] - sum[l]; l,r 是下标 return sum[r] - sum[l-1];// l r 是位置 }## 二 基础模板题实战### 2.1 【模板】静态区间和前缀和_牛客题霸_牛客网#这是地址【模板】静态区间和前缀和_牛客题霸_牛客网解析这道题目l r给的是位置 数据量很大要开long1234567891011121314151617181920212223242526272829javaimportjava.util.*;importjava.io.*;publicclassMain {publicstaticvoidmain(String[] args)throwsIOException {BufferedReader br newBufferedReader(newInputStreamReader(System.in));PrintWriter pw newPrintWriter(System.out);StreamTokenizer st newStreamTokenizer(br);st.nextToken();intn (int)st.nval;st.nextToken();intq (int)st.nval;int[] arr newint[n];for(inti 0; i n; i) {st.nextToken();arr[i] (int)st.nval;}long[] sum newlong[n1];sum[0] 0;for(inti 1; i n; i){sum[i] sum[i-1]arr[i-1];}for(inti 0; i q; i) {st.nextToken();intl (int)st.nval;st.nextToken();intr (int)st.nval;pw.println(sum[r]-sum[l-1]);}pw.flush();pw.close();br.close();}}如果不会流输入的话 用Scanner也行###2.2 题目给的是下标303. 区域和检索 - 数组不可变地址 303. 区域和检索 - 数组不可变class NumArray { public int[] sum; public NumArray(int[] nums) { sum new int[nums.length1]; sum[0] 0; for(int i1; inums.length; i){ sum[i] sum[i-1]nums[i-1]; } } public int sumRange(int left, int right) { return sum[right1]-sum[left]; } }### 2.3 字符串 加前缀和地址舞萌时间到_牛客题霸_牛客网解析 把String转换成arr就行 再用前缀和的模板123456789101112131415161718192021222324252627282930313233343536373839javaimportjava.io.*;publicclassMain {publicstaticintMAXN 1000001;publicstaticint[] arr newint[MAXN];publicstaticint[] sum newint[MAXN 1];publicstaticvoidf() {sum[0] 0;for(inti 1; i n; i) {sum[i] sum[i -1] arr[i -1];}}publicstaticString s1;publicstaticintn, q, l, r;publicstaticvoidmain(String[] args)throwsIOException {BufferedReader br newBufferedReader(newInputStreamReader(System.in));PrintWriter pw newPrintWriter(System.out);StreamTokenizer st newStreamTokenizer(br);s1 br.readLine();n s1.length();for(inti 0; i n; i) {if(s1.charAt(i) P)arr[i] 3;elseif(s1.charAt(i) p)arr[i] 2;elseif(s1.charAt(i) G)arr[i] 1;elsearr[i] 0;}f();q Integer.parseInt(br.readLine());for(inti 0; i q; i) {String s br.readLine();l Integer.parseInt(s.split( )[0]);r Integer.parseInt(s.split( )[1]);pw.println(sum[r] - sum[l -1]);}pw.flush();pw.close();br.close();}}## 三 前缀和与hash的结合### 3.1 题目简述在arr数组 给一个target 求和为target的子数组的最大长度地址未排序数组中累加和为给定值的最长子数组长度_牛客题霸_牛客网解析思路即求sum[i] -sum[j] target 应为有sum[0] 0; 所以长度为 I-J所以sum[j] sum[i]-k 用map来查我们用hashMap来存sum[j] 因为要求最长的区间 所以只要保存最早出现的位置map key 存sum[j] value存下表 ans来记录答案123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051importjava.util.*;importjava.io.*;publicclassMain {publicstaticintlongestSubarraySumK(int[] arr,inttarget) {intans 0, n arr.length;int[] sum newint[n 1];sum[0] 0;HashMapInteger, Integer map newHashMap();//必须放map.put(0,0);for(inti 1; i n; i) {sum[i] sum[i -1] arr[i -1];}for(inti 1; i n; i) {// sum[i] - sum[j] targetintneed sum[i] - target;if(map.containsKey(need)) {ans Math.max(ans, i - map.get(need));}if(!map.containsKey(sum[i])) {//最早出现的位置map.put(sum[i], i);}}returnans 0? -1: ans;}publicstaticvoidmain(String[] args)throwsIOException {BufferedReader br newBufferedReader(newInputStreamReader(System.in));PrintWriter pw newPrintWriter(System.out);StreamTokenizer st newStreamTokenizer(br);st.nextToken();intn (int)st.nval;st.nextToken();intk (int)st.nval;int[] arr newint[n];for(inti 0; i n; i) {st.nextToken();arr[i] (int)st.nval;}long[] sum newlong[n 1];sum[0] 0;for(inti 1; i n; i) {sum[i] sum[i -1] arr[i -1];}pw.println(longestSubarraySumK(arr, k));pw.flush();pw.close();br.close();}}### 3.2 题目1的变种 求arr所有子数组中正数与负数个数相等的最长子数组的长度。地址未排序数组中累加和为给定值的最长子数组系列问题补1_牛客题霸_牛客网实际题目是求正负数个数相等子数组 这个标题有问题解析思路我们只要把正数都变成 1 负数都变成 -1 题目就转化成求 和为0的最长子区间 就是题目1了1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950javaimportjava.util.*;importjava.io.*;publicclassMain {publicstaticintlongestSubarraySum0(int[] arr) {intans 0, n arr.length;for(inti 0; i n; i) {if(arr[i] 0) {arr[i] 1;}elseif(arr[i] 0) {arr[i] -1;}}int[] sum newint[n 1];sum[0] 0;HashMapInteger, Integer map newHashMap();map.put(0,0);for(inti 1; i n; i) {sum[i] sum[i -1] arr[i -1];}for(inti 1; i n; i) {// sum[i] - sum[j] targetintneed sum[i];if(map.containsKey(need)) {ans Math.max(ans, i - map.get(need));}if(!map.containsKey(sum[i])) {map.put(sum[i], i);}}returnans;}publicstaticvoidmain(String[] args)throwsIOException {BufferedReader br newBufferedReader(newInputStreamReader(System.in));PrintWriter pw newPrintWriter(System.out);StreamTokenizer st newStreamTokenizer(br);st.nextToken();intn (int)st.nval;int[] arr newint[n];for(inti 0; i n; i) {st.nextToken();arr[i] (int)st.nval;}pw.println(longestSubarraySum0(arr));pw.flush();pw.close();br.close();}}### 3.3 num数组不是0 就是 1 求 0 1个数相同的最长子区间地址 525. 连续数组 - 力扣LeetCode解析思路遍历数组把0 都变成-1 就变成了题目1class Solution { public int findMaxLength(int[] arr) { int n arr.length; for(int i0; in; i) { if(arr[i]0){ arr[i]-1; } } int ans Integer.MIN_VALUE; MapInteger, Integer map new HashMap(); int[] pre new int[n1]; pre[0] 0; for(int i1; in1; i) { pre[i] pre[i-1]arr[i-1]; } map.put(0, 0); for(int i1; in1; i) { int need pre[i]; if (map.containsKey(need)) { ans Math.max(ans, i-map.get(need)); } else { map.put(need, i); } } return ansInteger.MIN_VALUE?0:ans; } }### 3.4 求和为k的字数组的数量地址560. 和为 K 的子数组 - 力扣LeetCode解析思路即sum[i]-sum[j] targetmap存sum[j] 和sum[j]出现的次数sum[j] sum[i]-k; map来查当出现时 ans加上他出现的次数class Solution { public int subarraySum(int[] arr, int target) { int ans 0,n arr.length; int[] sum new int[n1]; sum[0] 0; HashMapInteger,Integer map new HashMap(); //必须放 map.put(0,1); for(int i1;in;i){ sum[i] sum[i-1]arr[i-1]; } for(int i1;in;i){ // sum[i] - sum[j] target int need sum[i]-target; //没有出现就加0 ansmap.getOrDefault(need,0); map.put(sum[i],map.getOrDefault(sum[i],0)1); } return ans; } }### 3.5 判断数组是否存在子数组的和为k的倍数 且区间长度大于等于2地址523. 连续的子数组和 - 力扣LeetCode解析思路即 (sum[i]-sum[j])%k0 并且 (j-i)2首先需要回一个减法同余原理a-b%k a%k-b%k所以我们子需要map来存sum[j]%k因为需要长度大于等于2 所以我们只存最早出现的class Solution { public boolean checkSubarraySum(int[] arr, int k) { if (arr null || arr.length 0) { return false; } MapInteger, Integer map new HashMap(); int n arr.length; int[] pre new int[n 1]; pre[0] 0; map.put(0, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] arr[i - 1]; } for (int i 1; i n; i) { int need pre[i]%k; if(map.containsKey(need)) { if(i - map.get(need) 2) { return true; } } //存最早的 else { map.put(need, i); } } return false; } }