如何改进一个算法来得到乘以等于一系列数之和的对数？

Question

我正在做下面的编程练习：我的朋友作弊吗？。声明是：

我的一个朋友取了一个从1到n的数列（其中n>0)。在这个序列中，他选择两个数字，a和B。他说a和b的乘积应该等于序列中所有数的和，不包括a和b。给出一个数字n，你能告诉我他从数列中排除了哪些数字吗？

该函数采用参数：n（n总是严格大于0)，并返回一个数组或字符串（取决于语言）的形式：

示例：

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());
    }
}

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]]

null

Answer 1

您不需要迭代您的对中的第二个数字。您可以只通过第一个pair来迭代，然后计算第二个pair。如果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)中工作。