商标转让费用_每日英语新闻_外贸网站如何推广优化_家电企业网站推广方案

问题：统计数组中连续子数组和为k的数量。
关键思路：

• 用哈希表记录前缀和出现的次数
• 遍历时若发现 sum - k 在哈希表中，则累加次数

代码实现：

def subarraySum(nums, k):prefix = {0: 1}  # 初始化：前缀和为0出现1次（空数组）sum_, count = 0, 0for num in nums:sum_ += numcount += prefix.get(sum_ - k, 0)  # 累加符合条件的子数组数量prefix[sum_] = prefix.get(sum_, 0) + 1  # 更新哈希表return count

关键点：

• 计算前缀和模 K 的余数，利用同余定理
• 处理负数余数：mod = (sum_ % K + K) % K

代码实现：

def subarraysDivByK(nums, K):prefix = {0: 1}sum_, ans = 0, 0for num in nums:sum_ += nummod = (sum_ % K + K) % K  # 修正负数余数ans += prefix.get(mod, 0)prefix[mod] = prefix.get(mod, 0) + 1return ans

核心思想：

• 构建二维前缀和数组时，利用容斥原理：
  $$prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1]$$

代码实现：

class NumMatrix:def __init__(self, matrix):m, n = len(matrix), len(matrix[0])self.prefix = [[0]*(n+1) for _ in range(m+1)]for i in range(m):for j in range(n):self.prefix[i+1][j+1] = self.prefix[i+1][j] + self.prefix[i][j+1] - self.prefix[i][j] + matrix[i][j]def sumRegion(self, r1, c1, r2, c2):return self.prefix[r2+1][c2+1] - self.prefix[r1][c2+1] - self.prefix[r2+1][c1] + self.prefix[r1][c1]

问题：找到含有相同数量0和1的最长子数组。
转化技巧：将0视为-1，问题转化为求和为0的最长子数组。

代码实现：

def findMaxLength(nums):prefix = {0: -1}  # 记录前缀和首次出现的下标sum_, max_len = 0, 0for i, num in enumerate(nums):sum_ += 1 if num == 1 else -1if sum_ in prefix:max_len = max(max_len, i - prefix[sum_])else:prefix[sum_] = ireturn max_len