统计距离为 k 的点对

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.

We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.

Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.

 

Example 1:

Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: We can choose the following pairs:
- (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5.
- (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.

Example 2:

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.

 

Constraints:

• 2 <= coordinates.length <= 50000
• 0 <= xi, yi <= 106
• 0 <= k <= 100

/* 
 * 题目思路：
 * 使用Java Streams，我们可以利用 IntStream.range 和 flatMap 方法。
 * 外层 IntStream.range 用于遍历第一个点的索引 i，
 * flatMap 中嵌套内层 IntStream.range 用于遍历第二个点的索引 j (j > i)，
 * mapToInt 用于计算异或距离，filter 用于筛选出等于 k 的距离，
 * count 方法用于统计满足条件的点对数量。
 */
import java.util.stream.IntStream;

public class Solution {
    public long countPairs(int[][] coordinates, int k) {
        return IntStream.range(0, coordinates.length)
            .flatMap(i -> IntStream.range(i + 1, coordinates.length)
                .map(j -> (coordinates[i][0] ^ coordinates[j][0]) +
                          (coordinates[i][1] ^ coordinates[j][1])))
            .filter(distance -> distance == k)
            .count();
    }
}

此题解采用了哈希表来记录遍历过的坐标点，以减少查找与计算时间。对于每个点(xj, yj)，通过枚举可能的(xi, yi)，计算可能满足条件的(xi XOR xj) + (yi XOR yj) = k的情况。这是通过固定一个点，然后为每个可能的a值（从0到k），计算出可能的xi和yi，然后在哈希表中查找是否有这样的(xi, yi)存在。如果存在，这意味着这对点满足距离为k。通过这种方式，每个点只需要考虑k+1种可能的配对点，大大减少了必须考虑的总配对数。

O(n*k)

O(n)