找到所有总和为零的三元组

Question

为了在列表中查找三元组，我使用了下面的组合函数。它按预期工作。 您能否建议任何其他优化函数来识别 kdb 列表中的三元组。

q)l:0 -2 5 -3 2
q)comb:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y where y>max x}\:l]}
q)r where (sum each r:comb[3;l]) = 0
-2 0  2
-3 -2 5

q)j:-2 6 1 3 -1 -4 0
q)r where (sum each r:comb[3;j]) = 0
-2 -1 3
-1 0  1
-4 -2 6
-4 1  3

Answer 1

这是一个优化函数，用于在列表中查找总和为零的三元组：

tripletsSumToZero:{[lst]
lst:asc lst;  / Sort the input list
triplets:();

n:count lst;

/ Fix one element and find other two elements using two pointers approach
for[i:0 to n-3;
    j:i+1;
    k:n-1;

    / Two pointers approach
    while[j<k;
        curr_sum:lst i,j,k;
        if[curr_sum=0;
            triplets,:lst i,j,k;
            j+:1;
            k-:1;
        elif[curr_sum<0;
            j+:1;
        :k-:1]
    ]
];

triplets

}

使用示例： q)三元组SumToZero -2 6 1 3 -1 -4 0

-4 -2 6
-1 0  1
-2 -1 3