Python任意正数数组和负数数组和为0则相消

Python任意正数数组和负数数组和为0则相消 前言

摸鱼时间点到问答板块，看到有意思的题目，好几个解答都没有被采纳，进去看看原题目地址，我也尝试回答了，题主说前提条件不完全满足，没有采纳，有点意思，花了小半天想了一下，记录一下解题思路。

题目

有两个长度不一的列表，一个装满了负数，一个装满正数
我想要同时遍历两个列表，当其中一个列表的和的值等于另一个列表时，就将这些数据标记或者删除。

例1[1,3,6][-2,-8]全部抵消(10)[][]例2[1,3,2,5,7][-2,-1,-3,-8]部分抵消(1,2,3)(-1-2-3)[5,7][-8]例3[2,5,17,9][-3,-3,-3]部分抵消(9)(-3-3-3)[1,5,17][] 解题思路

1. 逐个循环,相同剔除

   a=[1,2,3,4,4,5,56,67]
   b=[-1,-2,-4,-5,-100,-999,-888]
   for i in a[:]:
   	for k in b[:]:
   		if abs(k)==i:
   			a.remove(i)
   			b.remove(k)
   print(a,b)
   

   这样只是把相同的剔除了，但是类似如果一边是【-3，-5】，一边是【4，4】却无法抵冲

2. 两个列表总和，相加和为0：

   list1 = [11, 5, 17, 1, 2]
   list2 = [-2, -6, -11]
   print("列表1元素之和为: ", sum(list1))
   print("列表2元素之和为: ", sum(list2))
    
   if sum(list1)+sum(list2) == 0:
       print("相等")
   else:
       print("不相等")
   

   这样子精度不够，一旦总和对不上，所有数就都归类为对不上。
   但实际上有部份数是可以抵充的。。需要将那部分剔掉

3. 任意相等消除，那就是组数1找一个数，数组2多个数相加，和为0满足条件;于是，我开始写，1对1，1对2，1对多的消除方式，然后写下去发现不对劲，穷举法和递归好像都不能满足条件，本题目的比较是多对多形式的，我开始emo了

   def two_sum(nums, target):
       if len(nums) == 0:
           return -1,-1
       for index, item in enumerate(nums):
           for count in range(index+1, len(nums)):
               if (item + nums[count]) + target == 0:
                   return index,count
       return -1,-1
   
   if sum(list1)+sum(list2) == 0:
       print("相等")
   else:
       print("不相等")
       # 去除单个值抵消 1-1
       for i, val1 in enumerate(list1):
           for j, val2 in enumerate(list2):
               if val1 + val2 == 0:
                   del(list1[i])
                   del(list2[j])
       print(list1, "n",list2)
       # 去除两个值抵消 1-2
       for i, val1 in enumerate(list1):
           index, count = two_sum(list2, val1)
           if index>=0:
               print(list1[i],"==",list2[index],"+",list2[count])
               del(list2[index])
               del(list2[count-1])
               del(list1[i])
       for j, val2 in enumerate(list2):
           index, count = two_sum(list1, val2)
           if index>=0:
               print(list1[index],"+",list1[count],"==",list2[j])
               del(list1[index])
               del(list1[count-1])
               del(list2[j])
       print("n",list1, "n", list2,"n------n")
       
       # 去除多个值抵消 1-3
       ...
   

4. 高中数学老师突然给了我灵光一现，排列组合！
   是的，两个数组就是两个无穷数组的排列组合，然后任意组合相消的原理（怎么有点像高级连连看？？）
   例：[1,2,5,7]的子集排列组合有：[(1), (2), (5), (7), (1, 2), (1, 5), (1, 7), (2, 5), (2, 7), (5, 7), (1, 2, 5), (1, 2, 7), (1, 5, 7), (2, 5, 7)]
   这样就很好计算子集的和啦！于是我开始兴奋起来ヽ(✿ﾟ▽ﾟ)ノ

5. 不愧是我，用例就很不一般：[2,5,17,9] [-3,-3,-3] ,很明显，9可以消掉3个-3，
   换一个用例测试：[1,5,17,8] [-3,-3,-3] ，这次会消掉[1,5]和[-3,-3]剩下[17,8][-3]，
   可是我的代码陷入[17,8][]的循环中 (°ー°〃)
   check代码：发现剔除的时候不能按元素剔除，需要按位剔除。

源码

本身比较，（数组1的和）是否能和（数组2的和）相加为零；

• 是，全部消除
• 否，生成组数1的子集1，数组2的子集2；判断子集1的元素1是否与子集2的元素2相等
  • 是，删除抵消内容，抵消后的数组寻找子集是否相等，重复上一步
  • 否，没有值可以抵消

运行示例：

全部源码：

 
def son_list(list1,list2):
    # 子集
    res1=[]
    for i in range(len(list1)):
        res1 +=list(combinations(list1,i))
        res1 =[x for x in res1 if len(x) > 0]
    res2=[]
    for j in range(len(list2)):
        res2 +=list(combinations(list2,j))
        res2 =[x for x in res2 if len(x) > 0]
#     print("列表1的所有子集：",res1,"n列表2的所有子集：",res2)#所有排列组合
    return res1, res2
def sum_son_list(res1,res2):
    # 子集求和
    for i,item1 in enumerate(res1):
        isNegative = False
        for j,item2 in enumerate(res2):
            if isNegative == False:# 已找到负数的数字不重复匹配
                if sum(item1) + sum(item2) == 0:# 组合1的和+组合2的和 = 0
                    isNegative = True
#                     print("值相等的子集：",item1,"t",item2)
                    return list(item1),list(item2)
    return [],[]
def find_two_num(list1,list2):
    res1,res2 = son_list(list1,list2)
    a,b = sum_son_list(res1,res2)
#     print("n当前：",list1,list2)
    if len(a)<=0:
        print("n没有值可抵消")
#         print("n最终剩下的结果：",list1,list2)
        return False,list1,list2
    else:
        print("n可以抵消的值：",a,b)
        # 删除重复
        for i in a:
            isDelelet = False
            for ii,item11 in enumerate(list1):
                if isDelelet == False:# 按位删除数字
                    if(i == item11):
                        isDelelet = True
                        del(list1[ii])
        for j in b:
            isDelelet = False
            for jj,item22 in enumerate(list2):
                if isDelelet == False:
                    if(j == item22):
                        isDelelet = True
                        del(list2[jj])
        print("n抵消后的结果：",list1,list2)
        return True,list1,list2
def main(list1,list2):
    # 1.本身比较，全抵消
    if sum(list1)+sum(list2) == 0:
        print("全部相等，抵消后为空")
    else:
        # 2.找子集
        while True:
            isEnd,list1,list2 = find_two_num(list1,list2)
            if isEnd == False:
                break
if __name__ == "__main__":
    list1 = [2,5, 17, 1, 5,6] 
    list2 = [-3,-3,-3,-8] 
    print(list1,list2)
    main(list1,list2)
    print("=================")
    list1 = [1,4,6] 
    list2 = [-1,-3,-7] 
    print(list1,list2)
    main(list1,list2)
 

总结

当然这是由前到后按顺序的比较剔除，如果是如下示例，如果还有要求要最高位抵消时，其实可以抵消9而不是1，5 ；如果是这样的话，需要在剔除前，将数组排序一下，由大到小排列，则剔除最高位；由大到小排列，则剔除最低位。这个扩展就不写啦。