java寻找三个和可被给定数整除的数

Question

在java中，如何搜索一个数组并找到三个值的每个组合，它们的和可以被给定的数字（x）整除

换句话说，（n1+n2+n3）%x==0的每个组合

我知道这是一个使用三重for循环的简单解决方案，但我需要时间复杂度为O（N^2）的东西

有什么想法吗

Answer 1

1-哈希列表中的每个元素（元素%x）

2-对列表中的每一对元素求和（让我们称之为和y），并执行modded_y=y%x

3-检查哈希表中是否有x-moded_y。如果是，而不是另外两个数字中的一个，那么你就找到了一个可能的组合。不断迭代和散列你找到的组合，这样它们就不会重复

这叫做中间策略。

它的复杂度是O（n+（n^2*1））=O（n^2）

Answer 2

我将调用给定的数组A1

1）创建两个结构

&13；

；

struct pair{
int first;
int second;
bool valid; 
}

；

；

；

&13；

；

struct third{
int value;
int index; 
}

；

；

；

2）使用嵌套循环，初始化所有可能对的数组B1

3）通过B1循环。如果（A1[B1[i].first]+A1[B1[i].second]）%x==0，则设置B1[i]。对真有效

4）创建一个三分之一的数组A3，该数组存储A1中可被x整除的每个元素的索引和值

5）使用嵌套循环，遍历A3和B1的每个元素。如果B1。valid=true 打印A1[B1[i]。第一个]和A1[B1[i]。第二个]使用A1[A3.索引]中的元素

这样就可以在不使用任何三环的情况下提供所有组合