leetcode2021年度刷题分类型总结（一）前缀和思想 （python/c++）_leecode 前缀和习题

例一：1991. 找到数组的中间位置

1991. 找到数组的中间位置

方法一：暴力破解

分别在数组的首尾插入0，然后对数组进行遍历，每次遍历都计算所在位置左边和右边的和，并判断是否相等
若是，返回所在位置
若遍历完还没有找到左边和右边的和相等的序号，返回-1

class Solution(object):
    def findMiddleIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return 0

        nums.insert(0, 0)
        nums.insert(n + 1, 0)

        for i in range(1,n + 1):
            left = 0
            right = 0
            for j in range(i):
                left += nums[j]
            for k in range(i+1, n + 2):
                right += nums[k]

            if left == right:
                return i - 1

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：利用前缀和

首先计算遍历数组，计算每个位置的前缀和
分三种情况返回：
1）maxIndex==0,此时序号0右边的和为0，即(total-prefix[0])==0
2）maxIndex属于（0，n-1，(total-prefix[i])等于prefix[i-1]时返回i
3）maxIndex等于n-1，此时序号n-1左边的和为0，prefix[n-2]==0
若以上三种都不符合，返回-1
题目要求返回 最左边 的 middleIndex，所以return 0\return i\return n-1的顺序不能变

class Solution(object):
    def findMiddleIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        prefix=[0]*n
        if n==1:
            return 0
        prefix[0]=nums[0] #前缀和包括i指向的数，题目里分的左右不包括i指向的数
        for i in range(n):
            prefix[i]=prefix[i-1]+nums[i]
        #[4,0]\[0,4] 情况单拿出来考虑
        #题目要求返回 最左边 的 middleIndex，所以return 0\return i\return n-1的顺序还不能变
        total=prefix[n-1]
        if (total-prefix[0])==0:
            return 0
        for i in range(1,n):
            if (total-prefix[i])==prefix[i-1]: // ##total-prefix[i]等于i之后后半段的值
                return i
        if prefix[n-2]==0:
            return n-1

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

c++

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        //前缀和
        int total = accumulate(nums.begin(), nums.end(), 0); //头文件numeric
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

例二：2145. 统计隐藏数组数目

2145. 统计隐藏数组数目

方法一：遍历搜索

因为只要确定hidden[0],由于已知differences数组，那么整个hidden数组就已知，所以可以转换成求解合适的hidden[0]数量
hidden[0]采用遍历的方法一一尝试，如果尝试的hidden[0]满足接下来的每个数都符合在【lower,upper】内，则res+=1
这种方法可行，但时间复杂度高，超出时间限制

class Solution(object):
    def numberOfArrays(self, differences, lower, upper):
        """
        :type differences: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        n=len(differences)
        # hidden=[0]*(n+1)
        res=0
        
        
        def dfs(differences,left,right):
            # cnt=0
            # tmp_res=0
            for i in range(1,n):
                if differences[i]+right>=lower and differences[i]+right<=upper:
                    right=differences[i]+right
                    
                else:
                    return 0
            return 1
            
            
        for i in range(lower,upper+1):
            if differences[0]+i>=lower and differences[0]+i<=upper:
                left=i
                right=i+differences[0]
                res+=dfs(differences,left,right)
            
            
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

方法二：前缀和+反推

利用前缀和+反推的思想，通过hidden[0]+prefix[i]在【lower,upper】内，可推出hidden[0]在【lower-prefix[i]，upper-prefix[i]】内
遍历数组，得到具体的【lower-prefix[i]，upper-prefix[i]】范围，看hidden[0]有哪些还可以取的值
hidden[0]还可以取的值数目就是结果数

class Solution(object):
    def numberOfArrays(self, differences, lower, upper):
        """
        :type differences: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        n=len(differences)
        prefix=[0]*n
        prefix[0]=differences[0]
        for i in range(1,n):
            prefix[i]=prefix[i-1]+differences[i]
        
        left,right=lower,upper
        for i in range(n):
            left=max(left,lower-prefix[i])
            right=min(right,upper-prefix[i])

        if left>right:
            return 0
        else:
            return right-left+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23