3SUM问题(查找三元组)好于O(n ^ 2) [英] 3SUM problem (finding triplets) in better than O(n^2)

问题描述

请考虑以下问题:

给出一个未排序的整数数组，找到所有满足x ^ 2 + y ^ 2 = z ^ 2的三元组.

Given an unsorted array of integers, find all triplets that satisfy x^2 + y^2 = z^2.

例如，如果给定数组为 1、3、7、5、4、12、13 ，则答案应为 5、12、13 和3、4、5

For example if given array is 1, 3, 7, 5, 4, 12, 13, the answer should be 5, 12, 13 and 3, 4, 5

我建议以下算法的复杂度为O(n ^ 2):

I suggest the below algorithm with complexity O(n^2):

• 以降序排列O(nlogn)
• 对每个元素求平方O(n)

现在，它减少了在排序数组中找到所有三元组(a，b，c)从而使a = b + c的问题.

Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c.

面试官坚持要比O(n ^ 2)更好的解决方案.

The interviewer was insisting on a solution better than O(n^2).

我已阅读Wikipedia上的 3SUM问题，该问题强调可以在O(n + ulogu)，如果数字在[-u，u]范围内，则假设该数组可以表示为位向量.但我无法清楚了解进一步的解释.

I have read 3SUM problem on Wikipedia, which emphasizes problem can be solved in O(n+ulogu) if numbers are in range [-u,u] assuming the array can be represented as a bit vector. But I am not able to get a clear picture of further explanations.

有人可以帮我理解一个很好的例子吗?

Can someone please help me in understanding what is going on with a nice example?

推荐答案

首先.在最坏的情况下查找所有三元组是 O(n ^ 3).假设您有 n = 3k 个数字.其中K是3，k是4，k是5.

First of all. Finding all triplets in worst case is O(n^3). Suppose you have n=3k numbers. K of them are 3, k are 4 and k are 5.

3,....,3,4,....,4,5,.....5

有 k ^ 3 = n ^ 3/27 = O(n ^ 3)这样的三胞胎.只需打印它们就需要 O(n ^ 3)时间.

There are k^3 = n^3/27 = O(n^3) such triplets. Just printing them takes O(n^3) time.

接下来将以以下形式解释3SUM问题:

在 [-u; u] 范围内，每个数字都有 s_1，...，s_n 个.多少个三元组 a，b，c 有那个 a + b = c ?

There are numbers s_1, ..., s_n each of them in range [-u;u]. How many triplets a,b,c there are that a+b=c?

1. 正在转变.获取2 * u个数字 a_-u，...，a_0，a_1，... a_u . a_i 是数量 s_j ，即 s_j = i .这是在 O(n + u)

1. transforming. Get 2*u numbers a_-u, ..., a_0, a_1, ... a_u. a_i is amount of numbers s_j, that s_j = i. This is done in O(n+u)

res = a_0 * sum(i = -u..u，i =/= 0，C(a_i，2))+ C(a_0,3) a_0 = 0

建立一个多项式 P(x)= sum(i = -u ... u，a_i * x ^(i + u).

使用 FFT查找 Q(x)= P(x)* P(x).

请注意， Q(x)= sum(i = -2u..2u，b_i * x ^(i + 2 * u))，其中 b_i 是 s_u + s_k = i 的对 s_u ， s_k 的对数(这包括两次使用相同的数字).

Note that Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u)), where b_i is number of pairs s_u,s_k that s_u+s_k = i (This includes using same number twice).

对于所有偶数 i 都执行 b_i = b_i-a_(i/2).这将使用相同的号码删除两次.

For all even i do b_i = b_i - a_(i/2). This will remove using same number twice.

示例:为简单起见，我将假设数字范围为[0..u]，并且不会使用x的幂+ u.假设我们有数字 1,2,3 - a_0 = 0，a_1 = 1，a_2 = 1，a_3 = 1

Example: to be more simple, I will assume that range for numbers is [0..u] and won't use any +u in powers of x. Suppose that we have numbers 1,2,3 - a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1

• res = 0

P(x)= x + x ^ 2 + x ^ 3

Q(x)= x ^ 2 + 2x ^ 3 + 3x ^ 4 + 2x ^ 5 + x ^ 6

减去 b_2 = 0，b_3 = 2，b_4 = 2，b_5 = 2，b_6 = 0

res + = 0 * 1/2 + 2 * 1/2 + 2 * 0/2 + 2 * 0/2 + 6 * 0/2 = 1

这篇关于3SUM问题(查找三元组)好于O(n ^ 2)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！