457.环形数组是否存在循环

链接：457.环形数组是否存在循环
难度：Medium
标签：数组、哈希表、双指针
简介：如果 nums 中存在循环，返回 true ；否则，返回 false 。

题解 1 - cpp

• 编辑时间：2022-01-08
• 内存消耗：7MB
• 编程语言：cpp
• 解法介绍：对于每个起点进行双指针遍历。

class Solution {
   public:
    int getNext(int i, vector<int>& nums) {
        int delta = 1000 * nums.size(), n = nums.size();
        if (nums[i] < 0) delta *= -1;
        nums[i] += delta;
        return ((i + nums[i]) % n + n) % n;
    }
    bool circularArrayLoop(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i]) > 1000) continue;
            int p = i, q = i;
            do {
                p = getNext(p, nums);
                q = getNext(getNext(q, nums), nums);
            } while (p != q);
            int a = 0, b = 0, l = 0;
            do {
                if (nums[p] > 0)
                    a++;
                else
                    b++;
                l++;
                p = getNext(p, nums);
            } while (p != q);
            if (l > 1 && (a == 0 || b == 0)) return 1;
        }
        return 0;
    }
};

题解 2 - typescript

• 编辑时间：2021-08-07
• 执行用时：644ms
• 内存消耗：89MB
• 编程语言：typescript
• 解法介绍：bfs。

function circularArrayLoop(nums: number[]): boolean {
  const n = nums.length;
  const queue: [number, Set<number>][] = new Array(n).fill(0).map((_, i) => [i, new Set([i])]);
  while (queue.length) {
    const [idx, set] = queue.shift()!;
    const next = getNextIdx(idx, nums[idx]);
    if (next === idx) continue;
    if (set.has(next)) return true;
    if ((nums[idx] > 0 && nums[next] < 0) || (nums[idx] < 0 && nums[next] > 0) || set.size === n)
      continue;
    set.add(next);
    queue.push([next, set]);
  }
  return false;
  function getNextIdx(idx: number, step: number): number {
    let ans = idx + step;
    while (ans >= n) ans -= n;
    while (ans < 0) ans += n;
    return ans;
  }
}