java - 找到数组中所有元素对，使得它们的差的绝对值为 x

Question

我有一个未排序的数组，我想找到该数组中的所有对，使得它们的差(绝对值)给出 x。

例如，如果 x=8 并且我们有数组 {13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46} 我会得到: 值为 13 和 21 的索引 0 和 3(例如，13-21= | 8 |) 索引 1 和 5，值为 1 和 9 值为 -8 和 0 的索引 2 和 4 索引 6 和 10 的值为 -54 和 -46

我做了一个解决方案，但我不确定它是 O(n) 还是 O(n^2)。我试图避免嵌套循环，而是保留两个指针 i 和 j，但我仍然认为它是 O(n^2)？它的行为有点像嵌套循环。

int i = 0;
int j = 1;

    System.out.println("All pairs of elements of the array that subtract exactly to absolute value of " + x + " are:");

    while (i < A.length && j < A.length)
    {
        if (abs(A[i] - A[j]) == x)
        {
            System.out.println("Indices " + i + " & " + j + " with values " + A[i] + " & " + A[j]);
        }

        if (j != A.length - 1)
        {
            j++;
        } else if (i == A.length - 1)
        {
            return;
        } else
        {
            i++;
            j = i + 1;
        }

    }

Answer 1

It kind of behaves like a nested loop

这不仅仅是“某种程度上”——您已经手动编写了两个循环，j-loop 在逻辑上位于 i-loop 内。关键部分是:

i = 0
while i < limit {
    ...
    i += 1
}

和

j = 1
while j < limit {
    ...
    j = i+1
}

其中每一个都是 for 循环的“while”版本。

这与您的 if-else 逻辑相结合，可以很好地转换为

for i in 0 : limit {
    for j in i+1 : limit {
    }
}