不同长度含零列表消零并使两列表和相等的求解方案问询

问题描述 #

给定两个长度分别为n、m（n、m≥0）的列表，需要找到一种方案，将列表中的所有零替换为正整数（消除零），同时让处理后的两个新列表的和相等。若无法实现该目标，则返回-1。

示例：
输入：l1 = [1,2,0,0,4]，l2 = [3,0,7]
可行输出：l3 = [1,2,2,2,4]，l4 = [3,1,7]
此时sum(l3)=11，sum(l4)=11，且两个列表均无零。

思路分析 #

核心是通过给零分配正整数，让两列表的最终和相等。首先定义几个关键变量：

• sum1：l1去掉所有零后的元素和
• cnt1：l1中零的个数
• sum2：l2去掉所有零后的元素和
• cnt2：l2中零的个数

我们需要找到正整数集合（对应零的替换值），使得sum1 + sum(替换l1零的数值) = sum2 + sum(替换l2零的数值)。其中每个零的替换值至少为1，因此：

• 替换l1零的数值总和S1 ≥ cnt1
• 替换l2零的数值总和S2 ≥ cnt2

无解判断 #

1. 若两列表均无零（cnt1=0且cnt2=0）：仅当sum1=sum2时有解，否则无解。
2. 若仅l1无零（cnt1=0）：需满足sum1 ≥ sum2 + cnt2（因为sum1必须等于sum2 + S2，而S2≥cnt2），否则无解。
3. 若仅l2无零（cnt2=0）：需满足sum2 ≥ sum1 + cnt1（同理，sum2必须等于sum1 + S1，而S1≥cnt1），否则无解。
4. 若两列表均有零：一定存在可行解，可通过调整替换值的总和实现目标和相等。

解法步骤 #

1. 预处理列表：遍历两个列表，计算非零元素的和、零的个数，同时标记原列表中零的位置。
2. 判断无解情况：按照上述规则判断是否存在可行解，若无解直接返回-1。
3. 计算目标和与替换总和：选择T = max(sum1+cnt1, sum2+cnt2)作为最终目标和，此时：
   • S1 = T - sum1（l1零的替换值总和）
   • S2 = T - sum2（l2零的替换值总和）
     该T保证S1≥cnt1、S2≥cnt2，满足替换值为正整数的要求。
4. 分配替换值：给每个零先分配1，再将剩余的增量（S1-cnt1或S2-cnt2）加到任意一个零的替换值上（或分散到多个零，不影响结果正确性）。
5. 生成结果列表：将替换值填入原列表的零位置，得到最终的两个列表。

代码实现 #

def balance_lists(l1, l2):
    # 预处理l1：计算sum、cnt，标记零的位置
    sum1 = 0
    cnt1 = 0
    result1 = []
    for num in l1:
        if num != 0:
            sum1 += num
            result1.append(num)
        else:
            cnt1 += 1
            result1.append(None)  # 用None标记需要替换的零
    
    # 预处理l2
    sum2 = 0
    cnt2 = 0
    result2 = []
    for num in l2:
        if num != 0:
            sum2 += num
            result2.append(num)
        else:
            cnt2 += 1
            result2.append(None)
    
    # 判断无解情况
    if cnt1 == 0 and cnt2 == 0:
        return (result1, result2) if sum1 == sum2 else -1
    elif cnt1 == 0:
        if sum1 < sum2 + cnt2:
            return -1
        s2_total = sum1 - sum2
        # 分配替换值给l2的零
        assign2 = [1] * cnt2
        remaining = s2_total - cnt2
        if remaining > 0:
            assign2[0] += remaining
        # 替换result2中的None
        idx = 0
        for i in range(len(result2)):
            if result2[i] is None:
                result2[i] = assign2[idx]
                idx += 1
        return (result1, result2)
    elif cnt2 == 0:
        if sum2 < sum1 + cnt1:
            return -1
        s1_total = sum2 - sum1
        # 分配替换值给l1的零
        assign1 = [1] * cnt1
        remaining = s1_total - cnt1
        if remaining > 0:
            assign1[0] += remaining
        # 替换result1中的None
        idx = 0
        for i in range(len(result1)):
            if result1[i] is None:
                result1[i] = assign1[idx]
                idx += 1
        return (result1, result2)
    else:
        # 两列表均有零，计算目标和
        target_sum = max(sum1 + cnt1, sum2 + cnt2)
        s1_total = target_sum - sum1
        s2_total = target_sum - sum2
        
        # 分配l1的替换值
        assign1 = [1] * cnt1
        remaining1 = s1_total - cnt1
        if remaining1 > 0:
            assign1[0] += remaining1
        idx = 0
        for i in range(len(result1)):
            if result1[i] is None:
                result1[i] = assign1[idx]
                idx += 1
        
        # 分配l2的替换值
        assign2 = [1] * cnt2
        remaining2 = s2_total - cnt2
        if remaining2 > 0:
            assign2[0] += remaining2
        idx = 0
        for i in range(len(result2)):
            if result2[i] is None:
                result2[i] = assign2[idx]
                idx += 1
        
        return (result1, result2)

# 测试示例
l1 = [1,2,0,0,4]
l2 = [3,0,7]
print(balance_lists(l1, l2))
# 输出示例：([1, 2, 3, 1, 4], [3, 1, 7])，sum均为11，是可行解之一

说明 #

• 代码中默认将剩余增量加到第一个零的替换值上，得到的结果与示例不同，但同样满足要求。若需要和示例一致的分配方式（如将剩余增量平均分配），只需修改替换值的分配逻辑即可。
• 所有可行解均满足题目要求，方案不唯一。

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