前缀和专题学习

今天我们来说一下刷题时经常用到的前缀和思想，前缀和思想和滑动窗口会经常用在求子数组和子串问题上，当我们遇到此类问题时，则应该需要想到此类解题方式，该文章深入浅出描述前缀和思想，读完这个文章就会有属于自己的解题框架，遇到此类问题时就能够轻松应对。

下面我们先来了解一下什么是前缀和。

前缀和其实我们很早之前就了解过的，我们求数列的和时，Sn = a1+a2+a3+...an; 此时Sn就是数列的前 n 项和。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以我们完全可以通过 S5-S2 得到 a3+a4+a5 的值，这个过程就和我们做题用到的前缀和思想类似。我们的前缀和数组里保存的就是前 n 项的和。见下图

前缀和数组初始化：

 for (int i = 0; i < nums.length; i++) {
      presum[i+1] = nums[i] + presum[i];
 }
 

例如我们需要获取 nums[2] 到 nums[4] 这个区间的和，我们则完全根据 presum 数组得到

leetcode 724. 寻找数组的中心索引

724. 寻找数组的中心下标 - 力扣（LeetCode）

 本题比较简单，让前缀和等于总和减去后缀和，再减去当前下标对应的数即可：

class Solution {
    public int pivotIndex(int[] nums) {
        int presum = 0;
        //数组的和
        for (int x : nums) {
           presum += x;
        }      
        int leftsum = 0;
        for (int i = 0; i < nums.length; ++i) {
            //发现相同情况
            if (leftsum == presum - nums[i] - leftsum) {
                return i;
            }
            leftsum += nums[i];          
        }
        return -1;
    }
}
 

leetcode 560. 和为K的子数组

首先暴力求法直接枚举，双重循环：

class Solution {
    public int subarraySum(int[] nums, int k) {
         int len = nums.length;
         int sum = 0;
         int count = 0;
         //双重循环
         for (int i = 0; i < len; ++i) {
             for (int j = i; j < len; ++j) {
                 sum += nums[j];
                 //发现符合条件的区间
                 if (sum == k) {
                     count++;
                 }
             }
             //记得归零，重新遍历
             sum = 0;
         }
         return count;
    }
}

那么本题怎么使用前缀和呢？本题要求是某个连续子数组等于k，那么最简单的方式就是通过前缀和相减的方式得到不同的子数组。

比如对于pre[1]，那么我们让pre[len-1]去减pre[1]，即可得到i~n的子数组的和，让pre[len-2]去减pre[1]可以得到1~n-1的子数组和。就这样遍历判断是否为k即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        //前缀和数组
        int[] presum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            //这里需要注意，我们的前缀和是presum[1]开始填充的
            presum[i+1] = nums[i] + presum[i];
        }
        //统计个数
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i; j < nums.length; ++j) {
                //注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
                //所以这样就可以得到nums[i,j]区间内的和
                if (presum[j+1] - presum[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
 

但是这样的方法时间复杂度为O（n²），有没有办法可以优化呢？ 

前缀和+哈希算法

在做这题之前先来看看以前做过的这道题

class Solution {
    public int[] twoSum(int[] nums, int target) {
 
        HashMap map  = new HashMap<>();
        //一次遍历
        for (int i = 0; i < nums.length; ++i) {
            //存在时，我们用数组得值为 key，索引为 value
            if (map.containsKey(target - nums[i])){              
               return new int[]{i,map.get(target-nums[i])};
            }
            //存入值
            map.put(nums[i],i);
        }
        //返回
        return new int[]{};
    }
}
 

题目就是两数之和，通过使用哈希表的查找，将时间复杂度从（n²）降到了O（n）。在上面的代码中，我们将数组的值和索引存入 map 中，当我们遍历到某一值 x 时，判断 map 中是否含有 target - x，即可。

那么本题也可以用同样的做法。

回顾我们本题的目的是什么，就是找到和为k的子数组，不过我们将子数组以另外一种更易读的方式，也就是前缀和的形式来存储，此时子数组就变成了数组中两个遍历的差值。也就是说目的是找到一个数组中两个的差值为k。

即pre[m]-pre[n]=k;

那么我们逆向思考，对于每个pre[m]，想知道是否存在pre[n]满足上式，也就是说要满足pre[m]-k=pre[n]，只需要看看是否存在pre[n]满足这个式子即可。那么判断是否存在的方式就可以通过哈希表来进行O（1）时间复杂度的查找！

另一方面，由于pre[n]这个前缀数组，我们只需要在每次生成pre[i]的时候去对应的查找即可，并不需要将pre[n]保存下来以供后续使用，所以此处可以优化空间复杂度。

最终代码如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int count=0; 
        int pre=0;
        for(auto val:nums){
            pre+=val;
            if(mp.find(pre-k)!=mp.end())count+=mp[pre-k];
            if(mp.find(pre)==mp.end())mp[pre]=1;
            else mp[pre]++;
        }
        return count;
    }
};

除此之外，上面的代码中还有一点比较特别，mp[0]要设置成1，这是为什么呢？

因为假如k=6，然后出现了一个单一个数字的和就为6时，那么此时mp[6-6]=0;那么此时这组数据就不会被加入进去。

也就是说，原来的做法只考虑了两个或两个以上数字的加法的情况，那么为了使得单个数字也可以成立，或者说数组中假设说有0元素的存在。那么mp[0]=1也可以使得这种情况成立了。

leetcode1248. 统计优美子数组

接下来我们定义：

此处相比前缀和来说，前缀和是计算0~i子数组的和，此处是计算其有多少个奇数，本质是一样的。相当于遇到奇数则加1，遇到偶数则加0。

用这样的方式记录0~i的子数组有多少个奇数，然后想知道i~j的子数组有多少个奇数，只要相减即可：

既然本质和前缀和相同，那么此处也可以使用两数之和那样的思想。本题求的是哪些i到j的数组其奇数个数为k的，那么我们就使用哈希表来存储。

于是此处很简单，只需要将上面的这句代码改一下即可：

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int count=0; 
        int pre=0;
        for(auto val:nums){
            pre+=(val%2);
            if(mp.find(pre-k)!=mp.end())count+=mp[pre-k];
            if(mp.find(pre)==mp.end())mp[pre]=1;
            else mp[pre]++;
        }
        return count;
    }
};

leetcode 974 和可被 K 整除的子数组

首先我们知道，任意一个[i,j]区间的和，可以表示为：presum[j+1] - presum[i]。

那么我们想要判断区间 [i,j] 的和是否能整除 K，那么我们只需判断

(presum[j+1] - presum[i] ) % k 是否等于 0 即可，

我们假设 (presum[j+1] - presum[i] ) % k == 0；则

presum[j+1] % k - presum[i] % k == 0;

presum[j +1] % k = presum[i] % k ;

也就是说，只要两者对k取余数相等，就代表这两者的差能够整除k，例如12和7，这两个数字对5取余都是2，也就是说，12和7的差可以整除5。

所以对于presum[j+1]，只需要计算出其和k的余数，比如12计算出其对5的余数为2，那么所有以2为余数的数字都可以满足。 比如2、7、12。

但是我们不可能去一个个的找2、7、12……因为这有无数个，我们应该找其余数为2的前缀和，所以我们将数存储在map中，我们将存储在哈希表中的key不再是前缀和，而是前缀和对k的取余。

于是代码如下：

但是此处可以注意到存在问题，问题是对负数取模会存在问题，对负数取模还是负数，那么这样在寻找key的时候则无法寻找到，所以我们需要将取余变为负数的值让它变为正数：

于是代码如下：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int count=0; 
        int presum=0;
        for(auto val:nums){
            presum+=val;
            int remainder=(presum%k+k)%k;
            if(mp.find(remainder)!=mp.end())count+=mp[remainder];
            if(mp.find(remainder)==mp.end())mp[remainder]=1;
            else mp[remainder]++;
        }
        return count;
    }
};

leetcode 523 连续的子数组和

 

本题与上题很类似，也是子数组为k的倍数，但是有两点区别，区别在于这一题要求子数组长度至少为2，第二点是本题只需判断是否存在，而无需计算数量。

方法一：

在之前计数的方法上进行改动！

此处要求子数组长度至少为2，那我们只需要在最终计数完成后，剔除那种单个元素即组成k的倍数的情况！如果最终计数大于0，说明有子数组长度>=2的子数组满足这个条件的情况！

改动如下：

此处为什么设置为long？因为k很大，使用int会溢出，所以设为long，并且假如long和int型混用会导致还是int型，所以presum也得设置为long。

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int count=0; 
        long presum=0;
        for(auto val:nums){
            presum+=val;
            long remainder=(presum%k+k)%k;
            if(mp.find(remainder)!=mp.end())count+=mp[remainder];
            if(mp.find(remainder)==mp.end())mp[remainder]=1;
            else mp[remainder]++;
        }
        for(auto val:nums)if(val%k==0)count--;
        return count>0;
    }
};

 

方法二：

方法一仅仅只能对长度为2的数组进行限制，其实就是剔除了长度为1的情况，如果要求长度不止为2，那么第一种方法就不好做了。此处用一种更为通用的方法。

回顾上题中为了计算数量，我们在哈希表中存储的是key为余数，value为数量。而本题我们不需要计算数量，但是需要知道长度差，为了知道长度差，我们需要知道该余数所对应的下标是否和当前遍历到的index，差值为2。

（为什么要求长度差值>=2而不是>=1？这是因为这里计算下标的差值，是得到的是长度，是前面前缀和得到的那个key值所对应的下标，而这个下标不包含在子数组里：如这个例子中k=5，

数组23、2、 4、 6、7

前缀和23、25、29、35、42

其中第0个前缀和为23，取余为5，当下标到2时候，前缀和为29，取余也为5，此时下标的差值是：2-0，即长度为2

那如何解决呢？就是将哈希表中由原来的每个余数对应的key存储数量，改为存储下标即可。

代码如下：

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=-1;
        bool findFlag=false; 
        int presum=0;
        //int remainder=0;
        for(int i=0; isize();i++){
            presum+=nums[i];
            int remainder=(presum)%k;
            //remainder=presum%k;
            if(mp.find(remainder)!=mp.end()){
                int preIndex=mp[remainder];
                if(i-preIndex>=2)findFlag=true;
            }
            else if(mp.find(remainder)==mp.end()){
                mp[remainder]=i;//记录这个余数对应的下标，并且只有第一次时需要保存
            }
            
        }
        return findFlag;
    }
};

注意到上面的mp[0]=-1，此处比较难理解！理解不了此处可以暂时跳过！

原来mp[0]=1，是因为哈希表中存储的是次数，这是为了使得单个数字时也是一种解法。但是此处我们记录的是下标

我们需要添加一个mp[0]=-1，如果不添加，就会导致下面这种例子过不了：

为什么这种情况过不了呢？

换句话说，为什么设定mp[0]=-1就能过呢？

回想一下，我们判断子数组长度时，是通过当前下标减去原来同key第一次存储的下标，就得到了子数组长度。

如k=6，

数组    【1，1，2，4】

前缀和 【1，2，4，8】

key为  【1，2，4，2】

出现两个key相同时，子数组长度的计算方式如下：

此时子数组长度为2

但是例如k=6，数组[2,4]这种情况，此时

数组    【2，4】

前缀和 【2，6】

key      【2，0】

则此时导致map中最开始没有key为0的值。

那么我们就手动补一个，让mp[0]=-1

此时相减就能保证长度为2了。