1. 解题思路
这一题根据题意,显然我们可以将其先分为 n n n个原子partition,确保任意两个partition之间都不存在相同的元素,且每一个partition都不可再进一步切分。
此时,我们的答案总数就是 2 n − 1 2^{n-1} 2n−1。
因此,我们剩下的问题就是如何切分最小的原子partition了,而这个用一个滑动窗可即可快速得到,也没啥好多说的了。
2. 代码实现
给出python代码实现如下:
class Solution:
def numberOfGoodPartitions(self, nums: List[int]) -> int:
MOD = 10**9+7
locs = defaultdict(list)
for i, x in enumerate(nums):
locs[x].append(i)
cnt = 0
max_loc = 0
for i, x in enumerate(nums):
if i > max_loc:
cnt += 1
max_loc = locs[x][-1]
else:
max_loc = max(max_loc, locs[x][-1])
cnt += 1
ans = pow(2, cnt-1, mod=MOD)
return ans
提交代码评测得到:耗时912ms,占用内存45.1MB。