> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/356-line-reflection.md).

# 356 Line Reflection

## 356. [Line Reflection](https://leetcode.com/problems/line-reflection/description/)

## 1. Question

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

**Example 1:**

Givenpoints=`[[1,1],[-1,1]]`, return`true`.

**Example 2:**

Givenpoints=`[[1,1],[-1,-1]]`, return`false`.

**Follow up:**\
Could you do better than O(n2)?

## 2. Implementation

思路:

1. 如果存在一条线评分所有点，那么一个点和它关于这条线对称的点的x(横坐标值)和y(纵坐标)的值的和是一样的，包括最大和最小值，由于要求的是这个平分点的线是垂直于x轴的，所以我们只关心点的x值即可
2. 找出所有点中x值最大和最小的值，得到它们的和sum
3. 将每个点都以 x + "#" + y的形式计算它们的hashcode放入set里
4. 再一次遍历所有点，如果当前的点所对应的点 sum - x + "#" + y不在set里，说明不存在一条平分所有点的线

**(1) HashTable**

```java
class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Set<String> set = new HashSet<>();

        for (int[] point : points) {
            max = Math.max(max, point[0]);
            min = Math.min(min, point[0]);
            String code = point[0] + "#" + point[1];
            set.add(code);
        }

        int sum = min + max;
        for (int[] point : points) {
            String code = (sum - point[0]) + "#" + point[1];
            if (!set.contains(code)) {
                return false;
            }
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

**HashTable:** 时间复杂度O(n), 空间复杂度O(n)