假设你有两个唯一项目的列表，并且顺序无关紧要，你可以把它们都看作集合而不是列表

如果你考虑一个venn图，列表a作为一个圆，列表B作为另一个圆。那么这两者的交集就是常数池。

从A和B中删除该交叉点中的所有元素，A中剩下的所有元素都已删除，而B中剩下的任何元素都已添加。

因此，遍历A，查找B中的每一项。如果找到了，请将其从A和B中删除

然后A是删除的内容列表，B是添加的内容列表

我想。。。

[edit]好的，有了新的“仅2个容器”限制，同样的情况仍然存在：

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

那么你就不会构建一个新的列表，也不会破坏你的旧列表。。。但这将需要更长的时间，就像前面的例子一样，您可以在较短的列表上循环，并从较长的列表中删除元素。在这里你需要做两个列表

我认为我的第一个解决方案没有使用4个容器，它只销毁了两个；-）

我已经有一段时间没有这样做了，但我相信算法是这样的。。。

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

关于右列表与左列表的关系，删除包含删除的项目，添加现在包含新项目。

乔说了什么。而且，如果列表太大，无法放入内存，请使用外部文件排序实用程序或Merge排序。

缺少信息：如何定义添加/删除？例如，如果列表（A和B）在服务器A和服务器B上显示相同的目录，则这是同步的。如果我现在等待10天，再次生成列表并进行比较，我如何判断是否有内容被删除？我不能。我只能判断服务器A上有文件在服务器B上找不到，和/或相反。这是因为文件已添加到服务器a（因此在B上找不到该文件），还是因为文件已在服务器B上删除（因此在B上再也找不到文件），我无法仅通过文件名列表来确定。

对于我建议的解决方案，我只假设您有一个名为OLD的列表和一个名称为NEW的列表。在旧版上发现但在新版上没有发现的所有内容都已删除。在NEW上找到的但在OLD上没有找到的所有内容都已添加（例如，同一服务器上同一目录的内容，但列表是在不同日期创建的）。

此外，我将假设没有重复。这意味着列表中的每个项目都是唯一的：如果我将此项目与列表中的任何其他项目进行比较（无论这种比较如何），我总是可以说该项目比我将其与之进行比较的项目小或大，但永远不相等。例如，当处理字符串时，我可以按字典对它们进行比较，同一个字符串在列表中永远不会出现两次。

在这种情况下，最简单（但不一定是最好的解决方案）是：

1. 对旧列表进行排序。例如，如果列表由字符串组成，请按字母顺序对其进行排序。排序是必要的，因为这意味着我可以使用二进制搜索来快速找到列表中的对象，假设它确实存在（或者为了快速确定，它根本不存在于列表中）。如果列表未排序，则查找对象的复杂性为O（n）（我需要查看列表上的每一项）。如果对列表进行排序，则复杂性仅为O（logn），因为每次尝试匹配列表上的项目后，我总是可以排除列表上50%不匹配的项目。即使列表中有100个项目，找到一个项目（或检测该项目不在列表中）最多需要7次测试（还是8次？无论如何，远远少于100次）新列表不需要排序

2. 现在我们执行列表消除。对于NEW列表中的每个项目，尝试在OLD列表中找到该项目（使用二进制搜索）。如果找到该项目，请将该项目从旧列表中删除，也将其从新列表中删除。这也意味着消除过程越深入，列表就越小，因此查找将变得越来越快。由于从列表中删除项目不会影响列表的正确排序顺序，因此在删除阶段不需要使用OLD列表。

3. 在消除结束时，两个列表可能都是空的，在这种情况下它们是相等的。如果它们不为空，则仍在旧列表中的所有项目都是新列表中缺少的项目（否则我们已经删除了它们），因此这些是删除的项目。仍在NEW列表中的所有项目都是不在OLD列表中的项目（同样，我们以其他方式删除了它们），因此这些是添加的项目。

列表中的对象是否“唯一”？在这种情况下，我将首先构建两个映射（hashmap），然后扫描列表并查找映射中的每个对象。

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

很抱歉Ruby和Java混合使用了糟糕的元语言：-P

最后，removedElements将包含属于list1的元素，但不属于list2，addedElements[/strong>将包括属于list2的元素。

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}