我正在执行以下编程练习：Is my friend cheating?。该语句是：
我的一个朋友接受从1到n的数字序列（其中n>0）。在该序列中，他选择两个数字a和b。他说，a和b的乘积应等于序列中所有数字的和，不包括a和b。给定数字n，您能告诉我他从序列中排除的数字吗？
该函数采用参数：n（n始终严格大于0），并返回数组或字符串（取决于语言）形式：
[[（a，b），...]或[[a，b]，...]或{{a，b}，...}或or [{a，b}，...]
具有所有（a，b），它们是序列中可能删除的数字1至n。
[[（a，b），...]或[[a，b]，...]或{{a，b}，...}或...将被排序以“ a”的升序排列。
碰巧有几种可能（a，b）。功能如果没有可能的数字，则返回一个空数组（或一个空字符串）发现哪个将证明我的朋友没有说实话！ （进去这种情况下返回nil）。
示例：
removeNb（26）应该返回[[15，21]，[21，15]]
想法是：
Calculate sum of 1..n
For each number a
For each number b
if a*b=sum-(a+b)
add to result
而且我写了以下代码：
import java.util.*;
import java.util.stream.*;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
System.out.println("n: "+n);
long sum = LongStream.rangeClosed(1,n).sum();
List<long[]> result = new ArrayList<>();
System.out.println("sum: "+sum);
for(int a = 1; a <= n && a <= sum; a++){
System.out.println("a: "+a);
long prodMax = a*n;
long sumMax = sum-(a+n);
if(prodMax < sumMax){
System.out.println("prodMax: "+prodMax);
System.out.println("sumMax: "+sumMax);
continue;
};
for(int b = 1; b <= n && a*b <= (sum-(a+b)); b++){
if(a==b) continue;
System.out.println("b: "+b);
if(a*b == sum-(a+b)){
result.add(new long[]{a,b});
System.out.println("result: "+Arrays.deepToString(result.toArray()));
}
}
}
System.out.println("result: "+Arrays.deepToString(result.toArray()));
return result;
}
}
它通过了以下测试：
import static org.junit.Assert.*;
import java.util.List;
import java.util.ArrayList;
import org.junit.Test;
public class RemovedNumbersTest {
@Test
public void test12() {
List<long[]> res = new ArrayList<long[]>();
res.add(new long[] {15, 21});
res.add(new long[] {21, 15});
List<long[]> a = RemovedNumbers.removNb(26);
assertArrayEquals(res.get(0), a.get(0));
assertArrayEquals(res.get(1), a.get(1));
}
@Test
public void test14() {
List<long[]> res = new ArrayList<long[]>();
List<long[]> a = RemovedNumbers.removNb(100);
assertTrue(res.size() == a.size());
}
}
例如对于test12，跟踪为：
n: 26
sum: 351
a: 1
prodMax: 26
sumMax: 324
a: 2
prodMax: 52
sumMax: 323
a: 3
prodMax: 78
sumMax: 322
a: 4
prodMax: 104
sumMax: 321
a: 5
prodMax: 130
sumMax: 320
a: 6
prodMax: 156
sumMax: 319
a: 7
prodMax: 182
sumMax: 318
a: 8
prodMax: 208
sumMax: 317
a: 9
prodMax: 234
sumMax: 316
a: 10
prodMax: 260
sumMax: 315
a: 11
prodMax: 286
sumMax: 314
a: 12
prodMax: 312
sumMax: 313
a: 13
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 14
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
b: 23
b: 24
a: 14
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
a: 15
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
result: [[15, 21]]
a: 16
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 17
b: 18
b: 19
a: 17
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 18
a: 18
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 17
a: 19
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
a: 20
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
a: 21
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
result: [[15, 21], [21, 15]]
a: 22
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
a: 23
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 24
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 25
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
a: 26
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
result: [[15, 21], [21, 15]]
但是，当输入为大数时，例如n = 1000003，它将超时（执行时间大于16000ms）。
我也读过：
我们如何改进此算法？?
您无需遍历配对中的第二个数字。您只能迭代第一个对，然后计算第二个。如果x是第一个数字（您对其进行迭代），y是第二个数字（您要查找它），并且s是所有数字的总和，那么您只需要求解以下等式：
x * y = s - x - y <=>
(x + 1) * y = s - x <=>
y = (s - x) / (x + 1)
因此，如果(s - x) / (x + 1)是整数且不等于x，则它是成对的第二个数字。
通过此更改，您的算法将在O（n）而不是O（n ^ 2）中工作。