在数组中找到三元组 (a, b ,c)，使得 a + b + c = 0

Question

我想在一个数组中找到所有不同的三元组（a，b，c），使得 a + b + c = 0。我在 java 中实现了该算法，但是当输入很大时（例如 100,000 个零等），我得到了 TLE。对于 100,000 个零，它应该只输出 (0, 0, 0)。有人可以就如何加快速度提供一些想法吗？下面是我写的函数。它将一个数组作为输入并返回所有具有所需属性的唯一三元组作为列表。public List<List<Integer>> threeSum(int[] nums) {        Arrays.sort(nums);        List<List<Integer>> ll = new ArrayList<List<Integer>>();        for(int i = 0; i < nums.length - 1; i++){            int x = nums[i];            int start = i + 1;            int end = nums.length - 1;            int sum = -x;            while(start < end){                int y = nums[start] + nums[end];                if(y == sum){                    List<Integer> list = new ArrayList<Integer>();                    list.add(nums[start]);                    list.add(nums[end]);                    list.add(x);                    Collections.sort(list);                    ll.add(list);                }                if(y < sum)                    start++;                else                    end--;            }        }        return ll.stream()                 .distinct()                 .collect(Collectors.toList());    }

Answer 1

我认为你对时间复杂度无能为力。两个索引必须独立探索数组（起点/终点除外），而第三个索引可以受到约束，就像在您的算法中一样，这意味着复杂度为 O(n 2 )。这支配了数组的初步排序，即 O(n·log(n))，以及一个“去乘”步骤，即 O(n)。

我写了“demultiplication”，因为“deduplication”是不可取的：假设数组是[-1,-1,0,2]. 对其进行重复数据删除将消除唯一的解决方案。但是一个解不能包含超过两次的整数，除非它是0，在这种情况下[0,0,0]是一个解。所有出现两次以上的整数，或者在 的情况下出现三次0，都是冗余的，可以在排序之后和主算法之前一次性消除。

至于因素，可以通过将探索限制在有意义的范围内来改进。我会修改您的算法，使您移动直到它们相遇的一对索引从它们相遇的地方开始向外，直到较低的索引到达主要索引，或者较高的索引到达数组的末尾。扫描的起点可以在扫描中被记住，随着主索引向上移动，向下调整它。如果起始点（实际上是一对相邻索引的起始对）在当前范围之外，则可以省略扫描。找到初始起点是算法的附加部分，排序后可能是 O(log(n))，但非常简单的 O(n) 版本也可以。

抱歉，我现在没有时间将以上所有内容翻译成 Java 代码。我现在能做的就是记下数组排序后的“去乘”代码（未经测试）：

int len = 1;

int last = nums[0];

int count = 1;

for (int i = 1; i < nums.length; i++) {

    int x = nums[i];

    if (x != last) {

        nums[len++] = x;

        last = x;

        count = 1;

    } else if (count < 2 || x == 0 && count < 3) {

        nums[len++] = x;

        count++;

    }

}

// use len instead of nums.length from this point on

Answer 2

我看到的最重要的部分是，对于 100,000 个零的示例，您将针对每个可能的情况点击 if (y == sum) 块。这似乎是性能最差的情况，因为您永远不会跳过该块。

我能看到的最大改进是首先对您的输入进行重复数据删除。不幸的是，集合不起作用，因为我们仍然需要维护最多三个相同的条目。因此，我的建议是，在您排序之后，循环遍历输入数组，并且每当您连续遇到三个以上的数字副本时，删除额外的。他们不需要解决问题，只是浪费时间。

Answer 3

您可以创建一个List（其实现是ArrayList）来存储您已经拥有的组合。始终以以下格式存储新值

a,b,c

其中a <= b <= c

因此，每当您获得可能已经找到或尚未找到的组合时，请生成String相同格式的 a 并检查它是否存在于您的List. 如果是这样，那就不要add了。否则add它给你的List. 在此之后，您可以将找到的值转换为数值。如果你想加快速度，你可以创建一个class类似的：

class XYZ {

    public int x;

    public int y;

    public int z;

    public XYZ(int x, int y, int z) {

        this.x = x;

        this.y = y;

        this.z = z;

    }

    public isMatch(int x, int y, int z) {

        return (this.x == x) &&

               (this.y == y) &&

               (this.z == z);

    }

    public static boolean anyMatch(List<XYZ> list, int x, int y, int z) {

        for (XYZ xyz : list) {

            if (xyz.isMatch(x, y, z)) return true;

        }

        return false;

    }

    public static void addIfNotExists(List<XYZ> list, int x, int y, int z) {

        if (!anyMatch(list, x, y, z)) list.add(new XYZ(x, y, z));

    }

}

并且您可以将此类用于您的目的，只需确保x <= y <= z。

Answer 4

最后过滤非唯一三元组可以通过使用按排序顺序存储三元组的哈希表来消除，因此三元组的所有组合（具有不同排序）仅存储一次。

使用 hashmap/hashset 而不是 arraylist。

HashSet<List<Integer>> ll = new HashSet<List<Integer>>();

    .   .   .

    list.addAll(a,b,c)

    Collections.sort(list)

    ll.add(list)

除此之外，您还可以使用另一个查找表来确保 nums[] 中的每个重复项仅用于计算三元组一次。

lookup_table = HashMap();

for(int i = 0; i < nums.length - 1; i++){

    // we have already found triplets starting from nums[i]

    // eg. [-1,-1,0,1], we don't need to calculate

    // the same triplets for the second '-1'. 

    if (lookup_table.contains(nums[i]))

        continue;

    // Mark nums[i] as 'solved'

    lookup_table.add(nums[i])

    // usual processing here

    int x = nums[i];

或者，由于您的 nums[] 列表已经排序，您可以跳过重复项，无需另一个查找表。

i = 0;

while (i < nums.length - 1){

    // we have already found triplets starting from nums[i]

    // eg. [-1,-1,0,1], we don't need to calculate

    // the same triplets for the second '-1'.

    x = nums[i];

    // skip repeating items

    while (x == nums[i++]);

    // usual processing here

    .  .  .

    i++;

 }

然后您可以在最后将哈希集作为列表返回。