前言：简介前缀和知识
什么是前缀和？对于一个给定的数组nums,我们额外开辟一个前缀和数组进行预处理：
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++){
preSum[i + 1] = preSum[i] + nums[i];
}
前缀和数组中元素preSum[ i ]表示数组nums[0...i-1]的和。若求nums[ i ... j] 的和我们只需要计算preSum[j+1] - preSum[i]的值即可！见下面的例子：
//力扣题目--560 计算和为K的子数组，返回数组中有多少个子数组的和为K
//给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
class Solution {
public int subarraySum(int[] nums, int goal) {
int len = nums.length;
int[] sum = new int[len+1]; //前缀和数组
for(int i =1;i<=len;i++){
sum[i] = sum[i-1]+nums[i-1];
}
int result = 0; //结果集
for(int i =0; i<len; i++){
for(int j = i; j<len; j++){
if(sum[j+1] - sum[i] == k){
result++;
}
}
}
return result;
}
}这个解法的时间复杂度 O(N^2) 空间复杂度 O(N)，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。
对前缀和进行优化：借助hashMap,结合前缀和进行优化！
代码中的两层for循环，实际上做的事情就是寻找sum[ j ]与 sum[ i ]等于 K 的个数。
优化的思路是：直接记录下有几个 sum[j] 和 sum[i] - k 相等，直接更新结果，就避免了内层的 for 循环。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。
class Solution {
public int subarraySum(int[] nums, int goal) {
// 实现方法： 前缀和加hashmap实现
int len = nums.length;
if(len == 0 ){
return 0;
}
int[] sum = new int[len+1]; //前缀和数组
for(int i =1;i<=len;i++){
sum[i] = sum[i-1]+nums[i-1];
}
// map：前缀和 -> 该前缀和出现的次数
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>(); //实现前缀和数组元素sum[i] 与 其个数的映射
map.put(0,1);
int result = 0; //结果集
for(int i =0; i<len; i++){
//sum[i+1] 为前缀和nums[0...j]
if(map.containsKey(sum[i+1] - goal)){//判断map中是否含有sum[i+1] - goal的key值（前缀和）有则直接更新。
result += map.get(sum[i+1]-goal);//如果有则结果集加上个数
}
//把前缀和 nums[0...j]加入记录并且记录出现的次数
map.put(sum[i+1],map.getOrDefault(sum[i+1],0)+1);//更新map 次数加一
}
return result;
}
}时间复杂度由原来的 O(N^2) 降到了O（N）。下面是力扣的几个用到前缀和的例子。
一 、 1. 两数之和
1、题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
2、实现代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int[] preSum = new int[len+1];
preSum[0] = 0;
for(int i = 1 ; i<len; i++){
preSum[i+1] = preSum[i]+nums[i];
}
HashMap<Integer,Integer> map = new HashMap<>();
// map.put(0,1);
for(int i =0; i<len; i++){
//map:数组值-》数组下表
if(map.containsKey(target - nums[i])){
return new int[]{i,map.get(target-nums[i])};
}
map.put(nums[i],i);
}
return new int[]{};
}
}1、题目描述
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
2、 思路以及实现代码
class Solution {
public int pivotIndex(int[] nums) {
int sun = 0;
for(int num : nums){
sun+=num;//计算数组总和
}
int leftsum = 0; // 左半部分总和
for(int i = 0; i < nums.length; i++){
if(leftsum * 2 == sun - nums[i]){//判定第i位是否是中心下标，若是则应该满足条件：左半部分和*2 == 总和减去中心位置元素
return i;
}
leftsum += nums[i]; //左半部分和累加
}
return -1;
}
}1、题目描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
2、实现思路以及代码
class Solution {
public int subarraySum(int[] nums, int goal) {
// 实现方法： 前缀和加hashmap实现
int len = nums.length;
if(len == 0 ){
return 0;
}
int[] sum = new int[len+1]; //前缀和数组
for(int i =1;i<=len;i++){
sum[i] = sum[i-1]+nums[i-1];
}
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>(); //实现前缀和数组元素sum[i] 与 其个数的映射
map.put(0,1);
//细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
//例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
//输入：[3,1,1,0] k = 2时则不会漏掉
//因为presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),垫下底
int result = 0; //结果集
for(int i =0; i<len; i++){
if(map.containsKey(sum[i+1] - goal)){//判断map中是否含有sum[i+1] - goal的key值（前缀和）。
result += map.get(sum[i+1]-goal);//如果有则结果集加上个数
}
map.put(sum[i+1],map.getOrDefault(sum[i+1],0)+1);//更新map 次数加一
}
// for循环也可以这样写
/*
for(int i = 0; i<len; i++){
for(int j = i; j<len; j++){
if(sum[j+1] - sum[i] == goal) {
result++;
}
}
}
*/
return result;
}
}1、题目表述
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
2、实现思路以及代码
class Solution {
public int numberOfSubarrays(int[] nums, int goal) {
int len = nums.length;
int[] sum = new int[len+1];//前缀计数数组
for(int i =1;i<=len;i++){
sum[i] = sum[i-1]+(nums[i-1]%2);
}
Map<Integer,Integer> map =new HashMap<Integer,Integer>(); //奇数的个数以及奇数个数对应数组的个数
map.put(0,1);
int result = 0;
for(int i = 0; i< len; i++){
if(map.containsKey(sum[i+1] - goal)){
result+=map.get(sum[i+1] - goal);
}
map.put(sum[i+1],map.getOrDefault(sum[i+1],0)+1);
}
return result;
}
}1、 题目描述
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
示例：
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示：
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
2、解题思路以及实现代码
class Solution {
public int subarraysDivByK(int[] nums, int goal) {
int len = nums.length;
//a能被b整除,是说A除以B的结果是整数.
int[] sum = new int[len+1];//前缀计数数组
for(int i =1;i<=len;i++){
sum[i] =sum[i-1]+nums[i-1];
}
Map<Integer,Integer> map =new HashMap<Integer,Integer>(); //前缀和对goal的余数以及对应个数的映射
map.put(0,1);
int result = 0;
for(int i = 0; i< len; i++){
if(map.containsKey((sum[i+1]%goal + goal)%goal)){
result+=map.get((sum[i+1]%goal + goal)%goal);
}
map.put((sum[i+1]%goal + goal)%goal,map.getOrDefault((sum[i+1]%goal + goal)%goal,0)+1);
}
return result;
}
}