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

问题描述

我想在一个数组中找到所有不同的三元组（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());
    }

标签： javaalgorithm

我认为你对时间复杂度无能为力。两个索引必须独立探索数组（起点/终点除外），而第三个索引可以受到约束，就像在您的算法中一样，这意味着复杂度为 O(n ² )。这支配了数组的初步排序，即 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

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

问题描述

解决方案

推荐阅读