我在Codility中遇到过这个问题。看这个link .我设法解决了这个问题。然而，这给我留下了一些疑问。
这是使用三个 for 的代码。
public int solution(int[] A) {
Arrays.sort(A);
int k, count = 0;
for (int i = 0; i < A.length - 2; i++){
for (int j = i + 1; j < A.length - 1; j++){
for (k = j + 1; k < A.length; k++){
if (A[i] + A[j] > A[k]) break;
count += k - j - 1;
}
}
return count;
}
这是在最里面的for中使用while的代码。
public int solution(int[] A) {
// write your code in Java SE 8
Arrays.sort(A);
int k, count = 0;
for (int i = 0; i < A.length - 2; i++){
k = i + 2;
for (int j = i + 1; j < A.length; j++){
while (k < A.length && A[i] + A[j] > A[k]) {
k++;
}
count += k - j - 1;
}
}
return count;
}
上面的第一个解决方案并没有给我 Codility 满分，因为在大型测试用例中编译需要花费太多时间。但是，在使用 while 的第二个解决方案中，我得到了满分。为什么即使我在上面的这两个代码中都进行了三角形检查，也会出现这种情况？ for 和 while 跟这些有关系吗？
我也确实从第二个解决方案中了解到时间复杂度。这是 link . k 变量的初始化方式有所不同。这种差异是否会对这两个代码的性能产生巨大影响？
我想弄清楚到底是什么造成了这两个代码之间的区别。
最佳答案
for loop和 while loop与上述解决方案无关。事实上，我们可以修改第二个解决方案来制作while循环为 for循环如下:
public int solution(int[] A) {
Arrays.sort(A);
int k, count = 0;
for (int i = 0; i < A.length - 2; i++) {
k = i + 2;
for (int j = i + 1; j < A.length; j++) {
for( ; k < A.length; k++) {
if ( (A[i] + A[j]) <= A[k]) break;
}
count += k - j - 1;
}
}
return count;
}
实际上，你们两个解决方案背后的主要逻辑是完全不同的。
在第一个解决方案中:
我们正在使用三个 for 循环修复所有可能的三元组，并在前两个最小长度对的总和小于或等于第三对的总和时立即中断第三个循环，即它应该是 "if (A[i] + A[j] <= A[k]) break;"。 .因此，总体时间复杂度将为 O(n^3) .
第二种解决方案:
我们只修复两个 for loops并进行计算。您代码中的 while 循环仅针对每个 for loop 运行一次使用 i .由于数组被排序一次，这个解决方案背后的想法是，如果我们使用前两个 for loops 将两个值配对。 ，以及索引 i 处值的总和和 j是sum即sum = A[i] + A[j]如果它在索引 k 处遇到一个值大于或等于 sum然后是下一对 i和 j + 1 ，第三个指标肯定会大于之前的k因为索引值 j + 1大于索引 j 处的值即A[j] <= A[j + 1] .所以，第三个索引肯定比前面的k在右边。 .因此，第二个解决方案的总体复杂度为 O(n^2) .
关于java - 使用 for 和 while 在求解可能的三角形总数时的区别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53879401/