It is an interview question. We have an array of integers of size N containing element between 0 to N-1. It may be possible that a number can occur more than two times. The goal is to find pairs that sum to a given number X.
这是一个面试问题。我们有一个大小为N的整数数组,包含0到N-1之间的元素。数字可能会出现两次以上。目标是找到总和为给定数字X的对。
I did it using an auxiliary array having count of elements of primary array and then rearranging primary according auxiliary array so that primary is sorted and then searched for pairs.
我使用具有主数组元素计数的辅助数组,然后根据辅助数组重新排列主数据,以便对主数据进行排序,然后搜索对。
But interviewer wanted space complexity constant, so I told him to sort the array but it is nlogn time complexity solution. He wanted O(n) solution.
但是面试官希望空间复杂度不变,所以我告诉他对数组进行排序,但它是nlogn时间复杂度解决方案。他想要O(n)解决方案。
Is there any method available to do it in O(n) without any extra space?
有没有任何方法可以在没有任何额外空间的情况下在O(n)中执行此操作?
3 个解决方案
#1
6
No, I don't believe so. You either need extra space to be able to "sort" the data in O(n) by assigning to buckets, or you need to sort in-place which will not be O(n).
不,我不相信。您需要额外的空间才能通过分配给桶来“排序”O(n)中的数据,或者您需要就地排序而不是O(n)。
Of course, there are always tricks if you can make certain assumptions. For example, if N < 64K and your integers are 32 bits wide, you can multiplex the space required for the count array on top of the current array.
当然,如果你能做出某些假设,总有一些技巧。例如,如果N <64K且整数为32位宽,则可以在当前数组的顶部复用计数数组所需的空间。
In other words, use the lower 16 bits for storing the values in the array and then use the upper 16 bits for your array where you simply store the count of values matching the index.
换句话说,使用低16位来存储数组中的值,然后使用数组的高16位,只需存储与索引匹配的值的计数。
Let's use a simplified example where N == 8. Hence the array is 8 elements in length and the integers at each element are less than 8, though they're eight bits wide. That means (initially) the top four bits of each element are zero.
让我们使用一个简化的例子,其中N == 8.因此,数组长度为8个元素,每个元素的整数小于8,尽管它们是8位宽。这意味着(最初)每个元素的前四位为零。
0 1 2 3 4 5 6 7 <- index
(0)7 (0)6 (0)2 (0)5 (0)3 (0)3 (0)7 (0)7
The pseudo-code for an O(n) adjustment which stores the count into the upper four bits is:
用于将计数存储到高四位的O(n)调整的伪代码是:
for idx = 0 to N:
array[array[idx] % 16] += 16 // add 1 to top four bits
By way of example, consider the first index which stores 7. That assignment statement will therefore add 16 to index 7, upping the count of sevens. The modulo operator is to ensure that values which have already been increased only use the lower four bits to specify the array index.
举例来说,考虑存储7的第一个索引。因此,赋值语句将向索引7添加16,增加七次计数。模运算符是为了确保已经增加的值仅使用低四位来指定数组索引。
So the array eventually becomes:
所以数组最终变成:
0 1 2 3 4 5 6 7 <- index
(0)7 (0)6 (1)2 (2)5 (0)3 (1)3 (1)7 (3)7
Then you have your new array in constant space and you can just use int (array[X] / 16) to get the count of how many X values there were.
然后你将新数组放在常量空间中,你可以使用int(array [X] / 16)来获取有多少X值的计数。
But, that's pretty devious and requires certain assumptions as mentioned before. It may well be that level of deviousness the interviewer was looking for, or they may just want to see how a prospective employee handle the Kobayashi Maru of coding :-)
但是,这非常狡猾,需要如前所述的某些假设。很可能是面试官正在寻找的那种狡猾程度,或者他们可能只想看看未来的员工如何处理编码的小林丸:-)
Once you have the counts, it's a simple matter to find pairs that sum to a given X, still in O(N). The basic approach would be to get the cartestian product. For example, again consider that N is 8 and you want pairs that sum to 8. Ignore the lower half of the multiplexed array above (since you're only interested in the counts, you have:
一旦你有了计数,找到与给定X相加的对仍然是O(N)是一件简单的事情。基本方法是获得cartestian产品。例如,再次考虑N是8,你想要总和为8的对。忽略上面多路复用数组的下半部分(因为你只对计数感兴趣,你有:
0 1 2 3 4 5 6 7 <- index
(0) (0) (1) (2) (0) (1) (1) (3)
What you basically do is step through the array one by one getting the product of the counts of numbers that sum to 8.
你基本上做的是逐个遍历数组,得到总和为8的数字计数的乘积。
- For 0, you would need to add 8 (which doesn't exist).
- For 1, you need to add 7. The product of the counts is 0 x 3, so that gives nothing.
- For 2, you need to add 6. The product of the counts is 1 x 1, so that gives one occurrence of
(2,6). - For 3, you need to add 5. The product of the counts is 2 x 1, so that gives two occurrences of
(3,5). - For 4, it's a special case since you can't use the product. In this case it doesn't matter since there are no 4s but, if there was one, that couldn't become a pair. Where the numbers you're pairing are the same, the formula is (assuming there are
mof them)1 + 2 + 3 + ... + m-1. With a bit of mathematical widardry, that turns out to bem(m-1)/2.
对于0,您需要添加8(不存在)。
对于1,您需要添加7.计数的乘积为0 x 3,因此不提供任何内容。
对于2,您需要添加6.计数的乘积是1 x 1,因此给出一次(2,6)。
对于3,您需要添加5.计数的乘积是2 x 1,因此给出两次出现的(3,5)。
对于4,这是一个特例,因为您无法使用该产品。在这种情况下它没关系,因为没有4,但如果有一个,那就不能成为一对。如果您配对的数字相同,则公式为(假设有m个)1 + 2 + 3 + ... + m-1。通过一些数学widardry,结果是m(m-1)/ 2。
Beyond that, you're pairing with values to the left, which you've already done so you stop.
除此之外,你将左边的值与你已经完成的值配对,这样你就可以了。
So what you have ended up with from
那么你最终得到了什么
a b c d e f g h <- identifiers
7 6 2 5 3 3 7 7
is:
(2,6) (3,5) (3,5)
(c,b) (e,d) (f,d) <- identifiers
No other values add up to 8.
没有其他值加起来为8。
The following program illustrates this in operation:
以下程序说明了这一点:
#include <stdio.h>
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 4, 4, 4, 4};
#define SZ (sizeof(arr) / sizeof(*arr))
static void dumpArr (char *desc) {
int i;
printf ("%s:\n Indexes:", desc);
for (i = 0; i < SZ; i++) printf (" %2d", i);
printf ("\n Counts :");
for (i = 0; i < SZ; i++) printf (" %2d", arr[i] / 100);
printf ("\n Values :");
for (i = 0; i < SZ; i++) printf (" %2d", arr[i] % 100);
puts ("\n=====\n");
}
That bit above is just for debugging. The actual code to do the bucket sort is below:
上面的这一点仅用于调试。执行存储桶排序的实际代码如下:
int main (void) {
int i, j, find, prod;
dumpArr ("Initial");
// Sort array in O(1) - bucket sort.
for (i = 0; i < SZ; i++) {
arr[arr[i] % 100] += 100;
}
And we finish with the code to do the pairings:
我们完成代码来完成配对:
dumpArr ("After bucket sort");
// Now do pairings.
find = 8;
for (i = 0, j = find - i; i <= j; i++, j--) {
if (i == j) {
prod = (arr[i]/100) * (arr[i]/100-1) / 2;
if (prod > 0) {
printf ("(%d,%d) %d time(s)\n", i, j, prod);
}
} else {
if ((j >= 0) && (j < SZ)) {
prod = (arr[i]/100) * (arr[j]/100);
if (prod > 0) {
printf ("(%d,%d) %d time(s)\n", i, j, prod);
}
}
}
}
return 0;
}
The output is:
输出是:
Initial:
Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Counts : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4
=====
After bucket sort:
Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Counts : 0 2 1 2 5 3 1 0 1 2 0 0 0 0 0 0 0
Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4
=====
(2,6) 1 time(s)
(3,5) 6 time(s)
(4,4) 10 time(s)
and, if you examine the input digits, you'll find the pairs are correct.
并且,如果您检查输入数字,您会发现对是正确的。
#2
1
This may be done by converting the input array to the list of counters "in-place" in O(N) time. Of course this assumes input array is not immutable. There is no need for any additional assumptions about unused bits in each array element.
这可以通过在O(N)时间内将输入数组“就地”转换为计数器列表来完成。当然这假设输入数组不是不可变的。不需要对每个数组元素中的未使用位进行任何额外的假设。
Start with the following pre-processing: try to move each array's element to the position determined by element's value; move element on this position also to the position determined by its value; continue until:
从以下预处理开始:尝试将每个数组的元素移动到由元素值确定的位置;将此位置上的元素移动到由其值确定的位置;继续直到:
- next element is moved to the position from where this cycle was started,
- next element cannot be moved because it is already on the position corresponding to its value (in this case put current element to the position from where this cycle was started).
将下一个元素移动到此循环开始的位置,
下一个元素无法移动,因为它已经位于与其值对应的位置(在这种情况下,将当前元素放到此循环开始的位置)。
After pre-processing every element either is located at its "proper" position or "points" to its "proper" position. In case we have an unused bit in each element, we could convert each properly positioned element into a counter, initialize it with "1", and allow each "pointing" element to increase appropriate counter. Additional bit allows to distinguish counters from values. The same thing may be done without any additional bits but with less trivial algorithm.
在预处理之后,每个元素都位于其“适当”位置或“指向”其“适当”位置。如果我们在每个元素中都有一个未使用的位,我们可以将每个正确定位的元素转换为计数器,用“1”初始化它,并允许每个“指向”元素增加适当的计数器。附加位允许区分计数器和值。可以在没有任何额外位的情况下完成相同的操作,但使用较少的简单算法。
Count how may values in the array are equal to 0 or 1. If there are any such values, reset them to zero and update counters at positions 0 and/or 1. Set k=2 (size of the array's part that has values less than k replaced by counters). Apply the following procedure for k = 2, 4, 8, ...
计算数组中的值如何等于0或1.如果存在任何此类值,则将它们重置为零并更新位置0和/或1处的计数器。设置k = 2(数组的部分值小于值而k由计数器代替)。对k = 2,4,8,......应用以下程序
- Find elements at positions
k .. 2k-1which are at their "proper" position, replace them with counters, initial value is "1". - For any element at positions
k .. 2k-1with values2 .. k-1update corresponding counter at positions2 .. k-1and reset value to zero. - For any element at positions
0 .. 2k-1with valuesk .. 2k-1update corresponding counter at positionsk .. 2k-1and reset value to zero.
在位置k ... 2k-1处找到处于“正确”位置的元素,用计数器替换它们,初始值为“1”。
对于位置k ... 2k-1的任何元素,值为2 .. k-1更新位置2 .. k-1处的相应计数器并将值重置为零。
对于位置为0 ... 2k-1且值为k ... 2k-1的任何元素,在位置k ... 2k-1处更新相应的计数器并将值复位为零。
All iterations of this procedure together have O(N) time complexity. At the end the input array is completely converted to the array of counters. The only difficulty here is that up to two counters at positions 0 .. 2k-1 may have values greater than k-1. But this could be mitigated by storing two additional indexes for each of them and processing elements at these indexes as counters instead of values.
该过程的所有迭代一起具有O(N)时间复杂度。最后,输入数组完全转换为计数器数组。这里唯一的困难是位置0 .. 2k-1的最多两个计数器可能具有大于k-1的值。但是,可以通过为每个索引存储两个附加索引并将这些索引处理元素作为计数器而不是值来减轻这种情况。
After an array of counters is produced, we could just multiply pairs of counters (where corresponding pair of indexes sum to X) to get the required counts of pairs.
在生成一组计数器之后,我们可以将计数器对(其中对应的索引对总和为X)相乘以获得所需的对数。
#3
0
String sorting is n log n however if you can assume the numbers are bounded (and you can because you're only interested in numbers that sum to a certain value) you can use a Radix sort. Radix sort takes O(kN) time, where "k" is the length of the key. That's a constant in your case, so I think it's fair to say O(N).
字符串排序是n log n但是如果你可以假设数字是有界的(你可以因为你只对总和到某个值的数字感兴趣)你可以使用基数排序。基数排序需要O(kN)时间,其中“k”是密钥的长度。在你的情况下这是一个常数,所以我认为说O(N)是公平的。
Generally I would however solve this using a hash e.g.
但是,我通常会使用哈希来解决这个问题。
http://41j.com/blog/2012/04/find-items-in-an-array-that-sum-to-15/
Though that is of course not a linear time solution.
虽然这当然不是线性时间解决方案。
#1
6
No, I don't believe so. You either need extra space to be able to "sort" the data in O(n) by assigning to buckets, or you need to sort in-place which will not be O(n).
不,我不相信。您需要额外的空间才能通过分配给桶来“排序”O(n)中的数据,或者您需要就地排序而不是O(n)。
Of course, there are always tricks if you can make certain assumptions. For example, if N < 64K and your integers are 32 bits wide, you can multiplex the space required for the count array on top of the current array.
当然,如果你能做出某些假设,总有一些技巧。例如,如果N <64K且整数为32位宽,则可以在当前数组的顶部复用计数数组所需的空间。
In other words, use the lower 16 bits for storing the values in the array and then use the upper 16 bits for your array where you simply store the count of values matching the index.
换句话说,使用低16位来存储数组中的值,然后使用数组的高16位,只需存储与索引匹配的值的计数。
Let's use a simplified example where N == 8. Hence the array is 8 elements in length and the integers at each element are less than 8, though they're eight bits wide. That means (initially) the top four bits of each element are zero.
让我们使用一个简化的例子,其中N == 8.因此,数组长度为8个元素,每个元素的整数小于8,尽管它们是8位宽。这意味着(最初)每个元素的前四位为零。
0 1 2 3 4 5 6 7 <- index
(0)7 (0)6 (0)2 (0)5 (0)3 (0)3 (0)7 (0)7
The pseudo-code for an O(n) adjustment which stores the count into the upper four bits is:
用于将计数存储到高四位的O(n)调整的伪代码是:
for idx = 0 to N:
array[array[idx] % 16] += 16 // add 1 to top four bits
By way of example, consider the first index which stores 7. That assignment statement will therefore add 16 to index 7, upping the count of sevens. The modulo operator is to ensure that values which have already been increased only use the lower four bits to specify the array index.
举例来说,考虑存储7的第一个索引。因此,赋值语句将向索引7添加16,增加七次计数。模运算符是为了确保已经增加的值仅使用低四位来指定数组索引。
So the array eventually becomes:
所以数组最终变成:
0 1 2 3 4 5 6 7 <- index
(0)7 (0)6 (1)2 (2)5 (0)3 (1)3 (1)7 (3)7
Then you have your new array in constant space and you can just use int (array[X] / 16) to get the count of how many X values there were.
然后你将新数组放在常量空间中,你可以使用int(array [X] / 16)来获取有多少X值的计数。
But, that's pretty devious and requires certain assumptions as mentioned before. It may well be that level of deviousness the interviewer was looking for, or they may just want to see how a prospective employee handle the Kobayashi Maru of coding :-)
但是,这非常狡猾,需要如前所述的某些假设。很可能是面试官正在寻找的那种狡猾程度,或者他们可能只想看看未来的员工如何处理编码的小林丸:-)
Once you have the counts, it's a simple matter to find pairs that sum to a given X, still in O(N). The basic approach would be to get the cartestian product. For example, again consider that N is 8 and you want pairs that sum to 8. Ignore the lower half of the multiplexed array above (since you're only interested in the counts, you have:
一旦你有了计数,找到与给定X相加的对仍然是O(N)是一件简单的事情。基本方法是获得cartestian产品。例如,再次考虑N是8,你想要总和为8的对。忽略上面多路复用数组的下半部分(因为你只对计数感兴趣,你有:
0 1 2 3 4 5 6 7 <- index
(0) (0) (1) (2) (0) (1) (1) (3)
What you basically do is step through the array one by one getting the product of the counts of numbers that sum to 8.
你基本上做的是逐个遍历数组,得到总和为8的数字计数的乘积。
- For 0, you would need to add 8 (which doesn't exist).
- For 1, you need to add 7. The product of the counts is 0 x 3, so that gives nothing.
- For 2, you need to add 6. The product of the counts is 1 x 1, so that gives one occurrence of
(2,6). - For 3, you need to add 5. The product of the counts is 2 x 1, so that gives two occurrences of
(3,5). - For 4, it's a special case since you can't use the product. In this case it doesn't matter since there are no 4s but, if there was one, that couldn't become a pair. Where the numbers you're pairing are the same, the formula is (assuming there are
mof them)1 + 2 + 3 + ... + m-1. With a bit of mathematical widardry, that turns out to bem(m-1)/2.
对于0,您需要添加8(不存在)。
对于1,您需要添加7.计数的乘积为0 x 3,因此不提供任何内容。
对于2,您需要添加6.计数的乘积是1 x 1,因此给出一次(2,6)。
对于3,您需要添加5.计数的乘积是2 x 1,因此给出两次出现的(3,5)。
对于4,这是一个特例,因为您无法使用该产品。在这种情况下它没关系,因为没有4,但如果有一个,那就不能成为一对。如果您配对的数字相同,则公式为(假设有m个)1 + 2 + 3 + ... + m-1。通过一些数学widardry,结果是m(m-1)/ 2。
Beyond that, you're pairing with values to the left, which you've already done so you stop.
除此之外,你将左边的值与你已经完成的值配对,这样你就可以了。
So what you have ended up with from
那么你最终得到了什么
a b c d e f g h <- identifiers
7 6 2 5 3 3 7 7
is:
(2,6) (3,5) (3,5)
(c,b) (e,d) (f,d) <- identifiers
No other values add up to 8.
没有其他值加起来为8。
The following program illustrates this in operation:
以下程序说明了这一点:
#include <stdio.h>
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 4, 4, 4, 4};
#define SZ (sizeof(arr) / sizeof(*arr))
static void dumpArr (char *desc) {
int i;
printf ("%s:\n Indexes:", desc);
for (i = 0; i < SZ; i++) printf (" %2d", i);
printf ("\n Counts :");
for (i = 0; i < SZ; i++) printf (" %2d", arr[i] / 100);
printf ("\n Values :");
for (i = 0; i < SZ; i++) printf (" %2d", arr[i] % 100);
puts ("\n=====\n");
}
That bit above is just for debugging. The actual code to do the bucket sort is below:
上面的这一点仅用于调试。执行存储桶排序的实际代码如下:
int main (void) {
int i, j, find, prod;
dumpArr ("Initial");
// Sort array in O(1) - bucket sort.
for (i = 0; i < SZ; i++) {
arr[arr[i] % 100] += 100;
}
And we finish with the code to do the pairings:
我们完成代码来完成配对:
dumpArr ("After bucket sort");
// Now do pairings.
find = 8;
for (i = 0, j = find - i; i <= j; i++, j--) {
if (i == j) {
prod = (arr[i]/100) * (arr[i]/100-1) / 2;
if (prod > 0) {
printf ("(%d,%d) %d time(s)\n", i, j, prod);
}
} else {
if ((j >= 0) && (j < SZ)) {
prod = (arr[i]/100) * (arr[j]/100);
if (prod > 0) {
printf ("(%d,%d) %d time(s)\n", i, j, prod);
}
}
}
}
return 0;
}
The output is:
输出是:
Initial:
Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Counts : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4
=====
After bucket sort:
Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Counts : 0 2 1 2 5 3 1 0 1 2 0 0 0 0 0 0 0
Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4
=====
(2,6) 1 time(s)
(3,5) 6 time(s)
(4,4) 10 time(s)
and, if you examine the input digits, you'll find the pairs are correct.
并且,如果您检查输入数字,您会发现对是正确的。
#2
1
This may be done by converting the input array to the list of counters "in-place" in O(N) time. Of course this assumes input array is not immutable. There is no need for any additional assumptions about unused bits in each array element.
这可以通过在O(N)时间内将输入数组“就地”转换为计数器列表来完成。当然这假设输入数组不是不可变的。不需要对每个数组元素中的未使用位进行任何额外的假设。
Start with the following pre-processing: try to move each array's element to the position determined by element's value; move element on this position also to the position determined by its value; continue until:
从以下预处理开始:尝试将每个数组的元素移动到由元素值确定的位置;将此位置上的元素移动到由其值确定的位置;继续直到:
- next element is moved to the position from where this cycle was started,
- next element cannot be moved because it is already on the position corresponding to its value (in this case put current element to the position from where this cycle was started).
将下一个元素移动到此循环开始的位置,
下一个元素无法移动,因为它已经位于与其值对应的位置(在这种情况下,将当前元素放到此循环开始的位置)。
After pre-processing every element either is located at its "proper" position or "points" to its "proper" position. In case we have an unused bit in each element, we could convert each properly positioned element into a counter, initialize it with "1", and allow each "pointing" element to increase appropriate counter. Additional bit allows to distinguish counters from values. The same thing may be done without any additional bits but with less trivial algorithm.
在预处理之后,每个元素都位于其“适当”位置或“指向”其“适当”位置。如果我们在每个元素中都有一个未使用的位,我们可以将每个正确定位的元素转换为计数器,用“1”初始化它,并允许每个“指向”元素增加适当的计数器。附加位允许区分计数器和值。可以在没有任何额外位的情况下完成相同的操作,但使用较少的简单算法。
Count how may values in the array are equal to 0 or 1. If there are any such values, reset them to zero and update counters at positions 0 and/or 1. Set k=2 (size of the array's part that has values less than k replaced by counters). Apply the following procedure for k = 2, 4, 8, ...
计算数组中的值如何等于0或1.如果存在任何此类值,则将它们重置为零并更新位置0和/或1处的计数器。设置k = 2(数组的部分值小于值而k由计数器代替)。对k = 2,4,8,......应用以下程序
- Find elements at positions
k .. 2k-1which are at their "proper" position, replace them with counters, initial value is "1". - For any element at positions
k .. 2k-1with values2 .. k-1update corresponding counter at positions2 .. k-1and reset value to zero. - For any element at positions
0 .. 2k-1with valuesk .. 2k-1update corresponding counter at positionsk .. 2k-1and reset value to zero.
在位置k ... 2k-1处找到处于“正确”位置的元素,用计数器替换它们,初始值为“1”。
对于位置k ... 2k-1的任何元素,值为2 .. k-1更新位置2 .. k-1处的相应计数器并将值重置为零。
对于位置为0 ... 2k-1且值为k ... 2k-1的任何元素,在位置k ... 2k-1处更新相应的计数器并将值复位为零。
All iterations of this procedure together have O(N) time complexity. At the end the input array is completely converted to the array of counters. The only difficulty here is that up to two counters at positions 0 .. 2k-1 may have values greater than k-1. But this could be mitigated by storing two additional indexes for each of them and processing elements at these indexes as counters instead of values.
该过程的所有迭代一起具有O(N)时间复杂度。最后,输入数组完全转换为计数器数组。这里唯一的困难是位置0 .. 2k-1的最多两个计数器可能具有大于k-1的值。但是,可以通过为每个索引存储两个附加索引并将这些索引处理元素作为计数器而不是值来减轻这种情况。
After an array of counters is produced, we could just multiply pairs of counters (where corresponding pair of indexes sum to X) to get the required counts of pairs.
在生成一组计数器之后,我们可以将计数器对(其中对应的索引对总和为X)相乘以获得所需的对数。
#3
0
String sorting is n log n however if you can assume the numbers are bounded (and you can because you're only interested in numbers that sum to a certain value) you can use a Radix sort. Radix sort takes O(kN) time, where "k" is the length of the key. That's a constant in your case, so I think it's fair to say O(N).
字符串排序是n log n但是如果你可以假设数字是有界的(你可以因为你只对总和到某个值的数字感兴趣)你可以使用基数排序。基数排序需要O(kN)时间,其中“k”是密钥的长度。在你的情况下这是一个常数,所以我认为说O(N)是公平的。
Generally I would however solve this using a hash e.g.
但是,我通常会使用哈希来解决这个问题。
http://41j.com/blog/2012/04/find-items-in-an-array-that-sum-to-15/
Though that is of course not a linear time solution.
虽然这当然不是线性时间解决方案。