# 0335. 路径交叉
### 题目地址（335. 路径交叉）
### 题目描述
```
给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。
编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。
示例 1:
┌───┐
│ │
└───┼──>
│
输入: [2,1,1,2]
输出: true
示例 2:
┌──────┐
│ │
│
│
└────────────>
输入: [1,2,3,4]
输出: false
示例 3:
┌───┐
│ │
└───┼>
输入: [1,1,1,1]
输出: true
```
### 前置知识
* 滚动数组
### 公司
* 暂无
### 思路
符合直觉的做法是$O(N)$时间和$O(B)$空间复杂度的算法，其中 B 为障碍物的个数，也就是行走过程中经过的坐标点的个数。这种算法非常简单，关于空间复杂度为$O(B)$的算法可以参考我之前的[874.walking-robot-simulation](https://github.com/azl397985856/leetcode/blob/be15d243a3b93d7efa731d0589a54a63cbff61ae/problems/874.walking-robot-simulation.md)。 思路基本是类似，只不过 obstacles（障碍物）不是固定的，而是我们不断遍历的时候动态生成的，我们每遇到一个点，就将其标记为 obstacle。随着算法的进行，我们的 obstacles 逐渐增大，最终会增加到 $O(B)$。
但是题目要求我们使用空间复杂度为$O(1)$的做法。我们考虑进行优化。我们仔细观察发现，如果想让其不相交，从大的范围来看只有两种情况：
1. 我们画的圈不断增大。
2. 我们画的圈不断减少。
 （有没有感觉像迷宫？）
这样我们会发现，其实我们画最新一笔的时候，并不是之前画的所有的都需要考虑，我们只需要最近的几个就可以了，实际上是最近的五个，不过不知道也没关系，我们稍后会讲解。
红色部分指的是我们需要考虑的，而剩余没有被红色标注的部分则无需考虑。不是因为我们无法与之相交，而是我们`一旦与之相交，则必然我们也一定会与红色标记部分相交`。
然而我们画的方向也是不用考虑的。比如我当前画的方向是从左到右，那和我画的方向是从上到下有区别么？在这里是没区别的，不信我帮你将上图顺时针旋转 90 度看一下：
方向对于我们考虑是否相交没有差别。
当我们仔细思考的时候，会发现其实相交的情况只有以下几种：
> 图有误，第一种和第二种是同一种情况，换个角度看一样了。文字解释和代码已经更正
这个时候代码就呼之欲出了。
* 我们只需要遍历数组 x，假设当前是第 i 个元素。
* 如果 x\[i] >= x\[i - 2] and x\[i - 1] <= x\[i - 3]，则相交（第一种情况）
* 如果 i > 3 and x\[i - 1] == x\[i - 3] and x\[i] + x\[i - 4] == x\[i - 2]，则相交（第二种情况）
* 如果 i > 4 and x\[i] + x\[i - 4] >= x\[i - 2] and x\[i - 1] >= x\[i - 3] - x\[i - 5]\
and x\[i - 1] <= x\[i - 3] and x\[i - 2] >= x\[i - 4] and x\[i - 3] >= x\[i - 5] ，则相交（第三种情况）
* 否则不相交
### 关键点解析
* 一定要画图辅助
* 对于这种$O(1)$空间复杂度有固定的套路。常见的有：
1. 直接修改原数组
2. 滚动数组（当前状态并不是和之前所有状态有关，而是仅和某几个有关）。
我们采用的是滚动数组。如果你了解动态规划的滚动数组优化的话应该理解我的意思 。但是难点就在于我们怎么知道当前状态和哪几个有关。对于这道题来说，画图或许可以帮助你打开思路。另外面试的时候说出$O(B)$的思路也不失为一个帮助你冷静分析问题的手段。
感谢 [@saberjiang-b](https://leetcode-cn.com/u/saberjiang-b/) 指出的代码重复判断问题
### 代码
代码支持：Python3
Python3 Code:
```python
class Solution:
def isSelfCrossing(self, x: List[int]) -> bool:
n = len(x)
if n < 4:
return False
for i in range(3, n):
if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
return True
if i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]:
return True
if i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \
and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5]:
return True
return False
```
**复杂度分析**
其中 N 为数组长度。
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 45K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/335.self-crossing.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.