数组可清空性判断的算法优化及k=2、3时的专属算法探讨

问题定义 #

给定整数数组A、正整数k、整数tar，我们可以重复执行操作：删除数组中任意一段长度为k且元素和等于tar的连续子数组。需要判断是否能通过这类操作将数组完全清空。

示例说明 #

举个实际的例子：当A=[1,2,3,4]、k=2、tar=5时，我们可以先删除连续子数组[2,3]，数组变为[1,4]；接着删除剩下的[1,4]，就能把数组完全清空，因此算法应该返回True。

当前实现的动态规划算法 #

目前已经实现了时间复杂度为O(n²/k*C(n/k,k))的动态规划算法，核心思路是：
通过动态规划判断子数组A[i:j]是否可以被完全清空，枚举最后一次删除的子数组的元素位置——这一步的时间复杂度是O(C((j-i)/k,k))。

这里有一段k=3时的Python示例代码：

from functools import lru_cache
from itertools import accumulate

def solve(A, k, tar):
    # only works when k = 3
    assert k==3
    presum = list(accumulate(A, initial=0))
    @lru_cache(None)
    def judge(i, j):
        """ 判断子数组s[i:j]能否被完全删除 """
        l, remainder = divmod(j-i, k)
        if remainder != 0 or presum[j] - presum[i] != tar * l:
            return False
        if l <= 1:
            return True
        # 枚举最后一次删除的三个元素的位置
        # 寻找和为tar的三元组
        for a1 in range(i, j, 3):
            for a2 in range(a1+1, j, 3):
                for a3 in range(a2+1, j, 3):
                    if A[a1] + A[a2] + A[a3] == tar:
                        prv = i
                        flag = True
                        for nxt in [a1, a2, a3, j]:
                            if not judge(prv, nxt):
                                flag = False
                                break
                            prv = nxt + 1
                        if flag:
                            return True
        return False
    return judge(0, len(A))

print(solve([1,2,3,4,8,0],3,9))

待解决的问题 #

• 是否存在时间复杂度更优的替代算法？
• 是否有针对k=2和k=3这两种特定情况的专属优化算法？

贪心算法的局限性（反例） #

需要注意的是，贪心算法在k=3的场景下无法正确解决这个问题，比如下面这个测试用例：
A=[5,5,5,1,9,7,3,0,10,5,5,5,10,0,3,7,9,1,5,5,5]，tar=15，k=3。
如果用贪心策略优先删除最前面符合条件的子数组（比如开头的[5,5,5]），会导致后续剩余的数组无法被完全清空；而正确的做法是先删除中间某些符合条件的段，才能实现整体清空。这说明贪心在这里不适用。

内容的提问来源于stack exchange，提问作者Voyager