巧用前缀和

相关题目：

325. 和等于 k 的最长子数组长度

525. 连续数组

class Solution:
	"""
	325. 和等于 k 的最长子数组长度
	巧用前缀和数组，并优化前缀和数组为单变量
	"""
    def findMaxLength(self, nums: List[int], k: int) -> int:
        res = 0
        preSum = 0
        val2idx = dict()
        val2idx[0] = -1

        # 计算前缀和
        for idx, num in enumerate(nums):
            preSum += num
			need = preSum - k
            if need in val2idx:
                res = max(res, idx - val2idx[need])
            else:
                val2idx[need] = idx
        
        return res

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

class Solution:
	"""
	525. 连续数组
	这道题把0视作-1，题目就可转变为：寻找和为0的最长连续子数组
	"""
    def findMaxLength(self, nums: List[int]) -> int:
        res = 0
        preSum = 0
        val2idx = dict()
        val2idx[0] = -1

        # 计算前缀和
        for idx, num in enumerate(nums):
            preSum += (-1 if num == 0 else 1)

            if preSum in val2idx:
                res = max(res, idx - val2idx[preSum])
            
            else:
                val2idx[preSum] = idx
        
        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