这题我们的暴力做法就是o(n^2),但是根据数据量这样会超时，所以我们不能用暴力解法去解决
那么想一想双指针可以吗，不可以。为什么呢？因为他没有一个特性可以让他双指针跳过前面或者后面一个点。比如他们数组有顺序的情况下，还有一种性质，这个我也不知道怎么说，就是有个性质满足才能双指针，当前题目不能满足的话，那么我们就只能针对异或这个性质入手了，并且他的k的数只有100，那么只有100，那么其实就可以用k和异或这个性质同时入手
//异或的运算法则
假设x1^x2 = i,y1^y2 = (k - i),这样 x1^x2 + y1^y2 = k,根据运算法则得出
x1^x2^x2 = i^x2,y1^y2^y2 = (k - i)^y2
得出x1 = i^x2,y1 = (k - 2)^y2,我们的k和i是可以已知的，那么我们只要枚举i为1~k就行就可以求出
i和k-i，有了这个之后我们还是要遍历点的数组，因为我们其实是拿着点的坐标去暴力枚举i，k-i去试出来是否等于k，为什么这样可以呢？这是因为只要有一个点的坐标，然后暴力枚举出来等于k的可能性，那么枚举出等于k的数的话，我们就可以通过x1 = i^x2,y1 = (k - 2)^y2求出来x1，y1这个数了，那么我们怎么统计呢？现在外层循环是遍历点的数组，第二层循环是暴力枚举i为1~k，
那么第三层循环其实就是统计符合i < j，并且满足距离 为 (x1 XOR x2) + (y1 XOR y2) 这个
条件，我们怎么找到符合x1,y1的数呢，我们可以用哈希表进行预处理出来x1，y1的下标有哪些。
但是我们在统计的时候我们这样还是会出现o(n)的情况，因为会从头到尾遍历x1,y1这个数的下标，统计的话是统计x1,y1这个key的所有下标有几个小于外层循环遍历的原数组的下标。
所以我们是要优化统计这部分，我们先找到一个性质，key值x1，y1里的元素是不是顺序的，肯定是递增顺序的，这个不好证明，如果想去证明可以自己去证明，但是这是个很显然的性质，只要我们预处理的时候是按照下标顺序遍历的话，那么预处理出来的key值对应的元素也一定是按照顺序进行存储的，所以有了顺序性，那么我们就可以用二分来找到大于等于外层循环的下标的最小值，
然后统计出来有几个大于外层循环的下标元素个数。
所以时间复杂度就是O(n*k*logn);是绝对能过的
C++:最好用unordered_map,我是因为这个好像有点问题就不管了
#include <map>
#include <vector>
using namespace std;
class Solution {
public:
map<pair<int, int>, vector<int>> hashs;
int countPairs(vector<vector<int>>& coordinates, int k) {
int n = coordinates.size();
int ans = 0;
for (int i = 0; i < n; i++) {
pair<int, int> key = make_pair(coordinates[i][0], coordinates[i][1]);
hashs[key].push_back(i);
}
for (int i = 0; i < n; i++) {
int x2 = coordinates[i][0];
int y2 = coordinates[i][1];
for (int j = 0; j <= k; j++) {
int i1 = j;
int ki1 = k - j;
int x1 = (i1 ^ x2);
int y1 = (ki1 ^ y2);
auto it = hashs.find(make_pair(x1, y1));
if (it != hashs.end()) {
vector<int>& a = it->second;
int l = 0;
int r = a.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= i) {
r = mid;
} else {
l = mid + 1;
}
}
int find_index = 0;
if (a[l] < i) {
find_index = -1;
}
if (a[l] == i) {
ans += a.size() - l - 1;
} else if (find_index == -1) {
ans += 0;
} else {
ans += a.size() - l;
}
}
}
}
return ans;
}
};class Solution {
public int countPairs(List<List<Integer>> coordinates, int k) {
int n = coordinates.size();
int ans = 0;
Map<Pair<Integer, Integer>, List<Integer>> hashs = new HashMap<>();
for (int i = 0; i < n; i++) {
int x = coordinates.get(i).get(0), y = coordinates.get(i).get(1);
hashs.computeIfAbsent(new Pair<>(x, y), k1 -> new ArrayList<>()).add(i);
}
for (int i = 0; i < n; i++) {
int x2 = coordinates.get(i).get(0), y2 = coordinates.get(i).get(1);
for (int j = 0; j <= k; j++) {
int i1 = j, ki1 = k - j;
int x1 = (i1 ^ x2), y1 = (ki1 ^ y2);
List<Integer> a = hashs.getOrDefault(new Pair<>(x1, y1), null);
if (a != null) {
int l = 0, r = a.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (a.get(mid) >= i) {
r = mid;
} else {
l = mid + 1;
}
}
int find_index = 0;
if (a.get(l) < i) {
find_index = -1;
}
if (a.get(l) == i) {
ans += a.size() - l - 1;
} else if (find_index == -1) {
ans += 0;
} else {
ans += a.size() - l;
}
}
}
}
return ans;
}
}
