寻找零和的三元组

Question

我正在尝试解决 GeeksClasses 中的问题，但我的提交有问题。我的代码有效，但他们说您的程序花费的时间比预期的要多。

问题链接： https ://practice.geeksforgeeks.org/problems/find-triplets-with-zero-sum/1/?track=SPCF-Sorting&batchId=154

问题陈述：

给定一个整数数组。检查它是否包含总和为零的三元组。

输入：

输入的第一行包含一个整数T，表示测试用例的数量。然后是 T 个测试用例。每个测试用例的第一行包含一个整数 N，表示数组中元素的数量。每个测试用例的第二行包含数组的 N 个空格分隔值。

输出

对于每个测试用例，如果存在三元组，则输出为 1，否则为 0

预期辅助空间：O(1)

预期时间复杂度：O(n2)

例子：

输入：

2

5

0 -1 2 -3 1

3

1 2 3

输出：

1

0

这是我的代码

def isPair(arr,left,right,u):

    while left < right:

        if arr[left] + arr[right] < u:

            left += 1

        elif arr[left] + arr[right] == u:

            return True

        elif arr[left] + arr[right] > u:

            right -= 1

    return False

def findTriplets(a,n):

    #code here

    a = sorted(a)

    for i in range(n):

        if isPair(a,i+1,n-1,0-a[i]):

            return 1

    return 0

#driver code

if __name__=='__main__':

    t=int(input())

    for i in range(t):

        n=int(input())

        a=list(map(int,input().strip().split()))

        print(findTriplets(a,n))

Answer 1

这个问题看起来很有趣，这里有两个我们可以使用的观察结果。每个有效的三元组都是以下任一形式：(0, -x, x)或 (x, y, z) 使得 x 和 y 与 z 的符号相反并且 x + y = - z我会考虑一种更简单的输入形式，因为您的大部分输入对于两个整数列表的内容都是多余的，即。example_1 = [[0, -1, 2, -3, 1], [1, 2, 3]]应该导致[1, 0].鉴于我认为以下是一个相当快速/可读的解决方案：from itertools import combinationsdef solve_all(inputs):&nbsp; &nbsp; return [solve(i) for i in inputs]def solve(single_input):&nbsp; &nbsp; input_set = set(single_input)&nbsp; &nbsp; negatives_set = set(-x for x in single_input if x < 0)&nbsp; &nbsp; positives_set = set(x for x in single_input if x > 0)&nbsp; &nbsp; if 0 in input_set and len(negatives_set & positives_set) > 0:&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; if any(sum(c) in positives_set for c in combinations(negatives_set, 2)):&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; if any(sum(c) in negatives_set for c in combinations(positives_set, 2)):&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; return 0

Answer 2

public class FindTriplets{&nbsp; &nbsp; public static List<List<Integer>> findTriplets(int nums[]) {&nbsp; &nbsp; &nbsp; &nbsp; boolean found = false;&nbsp; &nbsp; &nbsp; &nbsp; List<Integer> triples = null;&nbsp; &nbsp; &nbsp; &nbsp; HashSet<Integer> set = null;&nbsp; &nbsp; &nbsp; &nbsp; HashSet<List<Integer>> tripleSet = new HashSet<List<Integer>>();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < nums.length - 1; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; set = new HashSet<Integer>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = i + 1; j < nums.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; found = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int x = -(nums[i] + nums[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (set.contains(x)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer [] temp = {x,nums[i],nums[j]};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.sort(temp);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; triples = new ArrayList<Integer>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; triples.add(temp[0]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; triples.add(temp[1]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; triples.add(temp[2]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; found = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; set.add(nums[j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(found==true){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tripleSet.add(triples);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return new ArrayList<List<Integer>>(tripleSet);&nbsp; &nbsp; }&nbsp; &nbsp;public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int arr[] = {0, -1, 2, -3, 1};&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; //int arr[] = {-1, 0, 1, 2, -1, -4};&nbsp; &nbsp; &nbsp; &nbsp; List<List<Integer>> triplets = findTriplets(arr);&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Triplets : "+triplets );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; }}