我可以在O(n)中解决这个问题吗?

以下是一个问题的片段:

给定一个整数数组, query ,您的服务必须按以下方式运行 跟随。每个整数都是要添加到或从中删除的项目ID 推车。

如果查询整数为正,则添加表示项目的整数 ID放在购物车后面。

如果整数为负,则删除第一个出现的整数 从车上。

在处理完所有内容后,报告一个代表最终购物车的数组 查询。保证最终购物车不是空的 查询中的整数不等于0。

例子

最初,购物车中有n=5件商品:

cart = [1, 2, 1, 2, 1]
queries = [-1, -1, 3, 4, -3]

步骤

查询	任务	购物车状态
1.	从购物车中删除前1个	[2, 1, 2, 1]
1.	从购物车中删除前1个	[2, 2, 1]
3.	将3添加到购物车	[2, 2, 1, 3]
4.	将4添加到购物车	[2, 2, 1, 3, 4]
3.	从购物车中删除前3个	[2, 2, 1, 4]

最终输出:

[2, 2, 1, 4]

我不知道如何从O(n^2)降到O(n) 有什么想法吗?

我的代码看起来像这样:

def findFinalCart(cart, queries):
    for num in queries:
        if num > 0:
            cart.append(num)  # Append new elements
        else:
            value = abs(num)
            for i, x in enumerate(cart):
                if x == value:
                    del cart[i] 
                    break 
    return cart