难度: Hard
Submission
运行时间: 181 ms
内存: 16.3 MB
class Solution:
# def splitArray(self, nums: List[int]) -> bool:
# n, pre = len(nums), list(accumulate(nums))
# for j in range(3, n-3):
# vis = {pre[i-1] for i in range(1, j-1) if pre[i-1]==pre[j-1]-pre[i]}
# for k in range(j+2, n-1):
# if pre[k-1]-pre[j] == pre[-1]-pre[k] and pre[-1]-pre[k] in vis:
# return True
# return False
def splitArray(self, nums: List[int]) -> bool:
# [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]
n = len(nums)
ps = [0]*(n+1)
for i in range(n):
ps[i+1] = ps[i] +nums[i]
# ps[i] = sum(nums[:i])
# ps[i]-ps[j] = sum(nums[j:i])
# ps[i+1] - ps[j] = sum(nums[j:i+1]) [j,i]
cache = collections.defaultdict(list) #倒着记录所有可能的最后一个数/surfix sum 对应的index
for k in range(n-2, 4, -1):
# [k+1, n-1]
d = ps[n] - ps[k+1]
cache[d].append(k)
visited = set()
for i in range(1, n-5): #要给后面三个subarray留出空间 (分割的ijk不计入) 所以 i后面至少留5个空位 n-5 n-1 n) -> n-5)
# i j k
# [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]
# a b c d
a = ps[i] - ps[0] #[0,i-1]
if a in visited: continue
for j in range(i+2, n-3):
b = ps[j] - ps[i+1] #[i+1, j-1]
if b != a: continue
# 对 a b 的部分还是暴力 n^2 要求 a == b
# 对剩下的部分 找surfix sum == b的所有坐标 （坐标需在j右侧且流出第三个数至少一格）这样最后一个数也是b了
# 然后检查第三个数是不是b
# 时间复杂度 虽然仍是三重for 但内层for的总共执行次数实际上是 O(n) 的 ？
# 对同一个b的值，
for k in cache[b]: #[k+1,n-1]
if k-1 < j+1: continue
c = ps[k] - ps[j+1] #[j+1,k-1]
if c == b:
return True
visited.add(b)
return False
for i in range(1, n-5): #要给后面三个subarray留出空间 (分割的ijk不计入) 所以 i后面至少留5个空位 n-5 n-1 n) -> n-5)
# i j k
# [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]
# a b c d
a = ps[i] - ps[0] #[0,i-1]
for j in range(i+2, n-3):
b = ps[j] - ps[i+1] #[i+1, j-1]
if b != a: continue
# 对 a b 的部分还是暴力 n^2 要求 a == b
# 对剩下的部分 找surfix sum == b的所有坐标 （坐标需在j右侧且流出第三个数至少一格）这样最后一个数也是b了
# 然后检查第三个数是不是b
# 时间复杂度 虽然仍是三重for 但内层for的总共执行次数实际上是 O(n) 的 ？
# 对同一个b的值，
for k in cache[b]: #[k+1,n-1]
if k-1 < j+1: continue
c = ps[k] - ps[j+1] #[j+1,k-1]
if c == b:
return True
return False
""" 暴力+前缀和
for i in range(n-5):
# i j k
# [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]
# a b c d
a = ps[i]
for j in range(i+1,n-3):
b = ps[j] - ps[i+1]
for k in range(j+1, n-1):
c = ps[k] - ps[j+1]
d = ps[n] - ps[k+1]
if a == b == c == d:
return True
return False
"""
Explain
这个题解的思路是将问题转化为寻找四个子数组和相等的问题。首先使用前缀和数组 ps 计算从数组开头到每个位置的元素和，方便快速计算任意区间和。然后枚举第一个分割点 i 和第二个分割点 j，计算前两个子数组的和 a 和 b。如果 a 和 b 相等，就在 j 右侧寻找满足区间和等于 b 的位置 k，这样四个子数组的和就都相等了。为了加速寻找过程，使用哈希表 cache 提前记录所有可能的最后一个子数组的和及其对应的右端点位置，避免再次遍历。同时使用 visited 集合记录已经检查过的 b 值，避免重复计算。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def splitArray(self, nums: List[int]) -> bool:
n = len(nums)
# 计算前缀和数组
ps = [0]*(n+1)
for i in range(n):
ps[i+1] = ps[i] +nums[i]
# 倒序记录所有可能的最后一个子数组和及其右端点位置
cache = collections.defaultdict(list)
for k in range(n-2, 4, -1):
d = ps[n] - ps[k+1]
cache[d].append(k)
visited = set()
# 枚举第一个分割点 i
for i in range(1, n-5):
a = ps[i] - ps[0] # 第一个子数组和
if a in visited: continue
# 枚举第二个分割点 j
for j in range(i+2, n-3):
b = ps[j] - ps[i+1] # 第二个子数组和
if b != a: continue
# 在 j 右侧寻找满足区间和等于 b 的位置 k
for k in cache[b]:
if k-1 < j+1: continue
c = ps[k] - ps[j+1] # 第三个子数组和
if c == b:
return True
visited.add(b)
return False
Explore
前缀和数组ps是一种常用的数据结构，它可以帮助快速计算任意子数组的和，从而显著降低时间复杂度。具体来说，ps[i]存储了从数组开始到下标i-1的所有元素的和。如果我们想计算从索引a到索引b的子数组和，可以直接通过ps[b+1] - ps[a]来得到，这样只需要O(1)的时间复杂度。在本题中，多次需要计算不同子数组的和，使用前缀和数组可以避免每次都重新遍历子数组来计算总和，提高了效率。
使用哈希表cache来存储子数组和及其右端点位置虽然可以加速查找过程，但也有一些缺点或限制。首先，哈希表可能导致额外的内存使用，尤其是当数组元素较多时，存储所有可能的子数组和及其位置需要较大的空间。其次，哈希表在处理哈希冲突时可能会稍微增加时间复杂度。此外，这种方法依赖于预先存储的数据，如果子数组和非常分散，可能导致哈希表中存储了大量的无用信息，这些信息实际上在后续的查找过程中并未被利用。
在遍历过程中，从索引1开始枚举第一个分割点i，是因为如果从0开始，则第一个子数组将为空数组，这不符合题目要求每个子数组至少包含一个元素的条件。从1开始，确保了至少第一个元素属于第一个子数组，从而满足题意。
第二个分割点j的起始位置是i+2而不是i+1的原因在于，分割点之间至少需要间隔一个元素，以保证每个子数组至少包含一个元素。如果j从i+1开始，那么第二个子数组将为空，这同样不符合题目要求。因此，j从i+2开始，保证了第二个子数组至少包含一个元素，同时允许算法正确地将数组分割成符合条件的四个子数组。