力扣：335. 路径交叉

难度 困难 遇到困难，睡大觉

题目描述

给你一个整数数组 distance 。

从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

示例 1：

输入：distance = [2,1,1,2]
输出：true

示例 2：

输入：distance = [1,2,3,4]
输出：false

示例 3：

输入：distance = [1,1,1,1]
输出：true

提示：

• \(1 <= distance.length <= 10^5\)
• \(1 <= distance[i] <= 10^5\)
  通过次数15,346 | 提交次数35,285

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/self-crossing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题如果只是单纯的做出来其实很简单，我最初的思路就是使用set去存储坐标数对pair，判断是否交叉只需要判断当前一步的坐标之前是否到达过即可，以下是代码实现：

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        int x = 0, y = 0, add_x = 0, add_y = 1, add_add_x = -1, add_add_y = -1, mem = 1, ite = 0;
        set<pair<int, int>> passes{make_pair(0, 0)};

        while (distance.size() != ite) {
            while (distance[ite]--) {
                x += add_x;
                y += add_y;
                passes.insert(make_pair(x, y));
                if (passes.size() == mem) return true;
                mem = passes.size();
            }
            add_x += add_add_x;
            add_y += add_add_y;
            add_add_x -= add_x * 2;
            add_add_y -= add_y * 2;
            ++ite;
        }

        return false;
    }
};

但是这种方法需要的时间很长，而力扣给出的第 28/29 个测试用例足足有十万个数，很明显会导致超时。

没办法，只能去看一下力扣官方给出的题解 面向题解编程了属于是，看完之后有看了一下评论，发现一个很好理解的评论：

xioacd99：

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        for(int i=3, l=x.size(); i<l; i++) {
            // Case 1: current line crosses the line 3 steps ahead of it
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;  
            // Case 2: current line crosses the line 4 steps ahead of it
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; 
            // Case 3: current line crosses the line 6 steps ahead of it
            else if(i>=5 && x[i-2]>=x[i-4] && x[i]+x[i-4]>=x[i-2] && x[i-1]<=x[i-3] && x[i-1]+x[i-5]>=x[i-3]) return true;
        }
        return false;
    }

/*              i-2
    case 1 : i-1┌─┐i
                └─┼─>
               i-3

                   i-2
    case 2 : i-1 ┌────┐
                 └─══>┘i-3
                 i  i-4      (i overlapped i-4)

    case 3 :   i-4
               ┌──┐i-5
               │i<┼─┐
            i-3│    │i-1
               └────┘
                i-2

*/
};

所以说这题的所有交叉情况可以分为内卷、重叠、交叉三种情况。

需要注意的是：第三种情况（交叉）还需要考虑 i-2 & i-4 的关系和 i-1 & i-3 的关系，以为你如果 i-2 小于 i-4或 i-3 小于 i-1 的话，这个路径中是没有交叉点的。

还有一点就是题目中所描述的持续移动在解题的过程中实际上是不需要考虑的。

所以最终的结果与xioacd99给出的结果一样：

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        for (int i = 3; i < distance.size(); ++i) {
            if (distance[i - 3] >= distance[i - 1]&&
                distance[i - 2] <= distance[i]) {
                return true;
            } else
            if (i >= 4&&
                distance[i - 3] == distance[i - 1]&&
                distance[i - 2] <= distance[i - 4] + distance[i]) {
                return true;
            } else
            if (i >= 5&&
                distance[i - 4] <= distance[i - 2]&&
                distance[i - 1] <= distance[i - 3]&&
                distance[i - 3] <= distance[i - 5] + distance[i - 1]&&
                distance[i - 2] <= distance[i - 4] + distance[i]) {
                return true;
            }
        }

        return false;
    }
};

该结果的用时和内存情况是12ms/18.1MB，超过了96.579%/92.895%，可以多思考一下原理，深入理解。