每日打卡-LeetCode-457-环形数组是否存在循环

环形数组是否存在循环

class Solution {
 public:
  bool circularArrayLoop(vector<int>& nums) {
    int n = nums.size(), Base = 10000;
    // 遍历每个节点
    for (int i = 0; i < n; i++) {
      int last = -1;
      // 用指针 k 指向当前节点
      int k = i;
      int t = nums[i] > 0;
      int S = Base + i;
      do {
        // 计算从当前节点能够跳到下一个节点的编号
        int p = ((k + nums[k]) % n + n) % n;
        // 当前节点记录的值
        last = nums[k];
        // 标记当前节点为已访问
        nums[k] = S;
        // 跳到下一个节点
        k = p;
        // 只要没跳回 i，且下一个节点没被访问过，且下一个节点的符号与当前节点相同，就继续循环
      } while (k != i && nums[k] < Base && (t ^ (nums[k] > 0)) == 0);
      // 如果不是自环且从 i 出发又跳回了当前节点，那么返回 true
      if (last % n && nums[k] == S) return true;
    }
    return false;
  }
};