题目地址：

https://www.lintcode.com/problem/number-pair-statistics/description

给定一个列表，每个元素是一个平面上的点的坐标。问有多少个点对$p_1,p_2$使得$p_1.x+p_2.x$和$p_1.y+p_2.y$都是偶数。

将每个点按照其$x$和$y$坐标的奇偶性分类，分成四类，即偶偶，偶奇，奇偶，奇奇，容易看出，每个类的内部的任意两点都满足要求，并且不同类的两个点都不满足要求。如果某一类的点的个数是$n$，则这个类能贡献出的满足条件的点对个数就是$n(n-1)/2$。累加起来即可。这里可以将四类做个编号，分别编号为二进制的$00,01,10,11$。代码如下：

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Solution { /** * @param p: the point List * @return: the numbers of pairs which meet the requirements */ public int pairNumbers(Point[] p) { // Write your code here Map<Integer, List<Point>> map = new HashMap<>(); for (int i = 0; i < 4; i++) { map.put(i, new ArrayList<>()); } for (Point point : p) { int b1 = point.x % 2, b2 = point.y % 2; map.get((b1 << 1) + b2).add(point); } int res = 0; // 累加答案 for (int i = 0; i < 4; i++) { int size = map.get(i).size(); res += size * (size - 1) / 2; } return res; } } class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } }

时空复杂度$O(n)$。