What is the core pattern in the "Count Pairs of Points With Distance k" problem?

The core pattern in this problem is using array scanning combined with hash lookups to efficiently find pairs of points that meet the distance condition defined by XOR operations.

How does the XOR operation help in solving the problem?

The XOR operation simplifies the calculation of distances between points, allowing for faster lookups of potential pairs without directly comparing all point pairs.

What is the time complexity of the solution?

Using a hash table for constant-time lookups, the time complexity of the solution is O(n), where n is the number of points.

Can this problem be solved without using a hash table?

While possible, solving the problem without a hash table would result in a slower, brute force solution with O(n^2) time complexity.

What are some edge cases to consider for this problem?

Edge cases include handling points with identical coordinates, ensuring that the XOR operation correctly handles these scenarios, and managing cases where the distance k is zero.

#2857

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计距离为 k 的点对

给你一个二维整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [x i , y i ] 是第 i 个点在二维平面里的坐标。我们定义两个点 (x 1 , y 1 ) 和 (x 2 , y 2 ) 的距离为 (x1 XOR x2) + (y1 XOR …

数组哈希表位运算

题目描述

给你一个二维整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [x_i, y_i] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x₁, y₁) 和 (x₂, y₂) 的距离为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：以下点对距离为 k ：
- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

示例 2：

输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出：10
解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。

提示：

2 <= coordinates.length <= 50000
0 <= x_i, y_i <= 10⁶
0 <= k <= 100

lightbulb

解题思路

方法一：哈希表 + 枚举

我们可以用一个哈希表 $cnt$ 统计数组 $coordinates$ 中每个点出现的次数。

接下来，我们枚举数组 $coordinates$ 中的每个点 $(x_2, y_2)$ ，由于 $k$ 的取值范围为 $[0, 100]$ ，而 $x_1 \oplus x_2$ 或 $y_1 \oplus y_2$ 的结果一定大于等于 $0$ ，因此我们可以在 $[0,..k]$ 范围内枚举 $x_1 \oplus x_2$ 的结果 $a$ ，那么 $y_1 \oplus y_2$ 的结果就是 $b = k - a$ 。这样一来，我们就可以计算出 $x_1$ 和 $y_1$ 的值，将 $(x_1, y_1)$ 出现的次数累加到答案中。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $coordinates$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        cnt = Counter()
        ans = 0
        for x2, y2 in coordinates:
            for a in range(k + 1):
                b = k - a
                x1, y1 = a ^ x2, b ^ y2
                ans += cnt[(x1, y1)]
            cnt[(x2, y2)] += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of XOR operations and how they can be applied to solve the problem.
question_mark
Assess familiarity with efficient array scanning combined with hash lookups to optimize performance.
question_mark
Check if the candidate can explain the reduction of problem complexity through hash map usage.

warning

常见陷阱

外企场景

error
Overcomplicating the problem with brute force solutions that do not scale to large input sizes.
error
Forgetting to utilize the XOR properties, which leads to unnecessary computations when checking point pairs.
error
Not handling edge cases properly, such as coordinates with the same values or zero distance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle a non-zero distance threshold, testing for pairs within a specific distance range.
arrow_right_alt
Extend the problem by adding constraints where points may have negative coordinates.
arrow_right_alt
Adjust the approach for real-time updates by adding or removing points and recalculating the count of valid pairs.

help

常见问题

外企场景

继续练习

#2869 收集元素的最少操作次数 #2897 对数组执行操作使平方和最大 #2932 找出强数对的最大异或值 I