วงจรในอาร์เรย์วงกลม (Circular Array Loop) ใน C++

วงจรในอาร์เรย์วงกลม (Circular Array Loop)

ให้อาร์เรย์วงกลม nums ที่มีค่าบวกและลบ ค่าบวก k หมายถึงก้าวไปข้างหน้า k ก้าว ค่าลบ -k หมายถึงก้าวถอยหลัง k ก้าว ตรวจสอบว่ามีวงจร (cycle) หรือไม่ วงจรต้องเริ่มและจบที่ index เดียวกัน และความยาว > 1

ตัวอย่าง: [2,-1,1,2,2] → true (วงจร 0→2→3→0 ความยาว 3)

ขั้นตอนการแก้ปัญหา (Fast & Slow Pointers)

1. n = nums.size(), ถ้า n < 2 คืนค่า false
2. ปรับค่า nums[i] %= n ทุกตัว
3. วนทุก index i:
   • ถ้า nums[i] == 0 ข้าม (visited แล้ว)
   • ใช้ slow/fast pointers ตรวจจับ cycle:
     • slow = i, fast = i
     • วนในขณะที่ทิศทางเดียวกัน (nums[slow]*nums[fast] > 0 และ nums[next(fast)]*nums[slow] > 0):
       • slow = next(slow), fast = next(next(fast))
       • ถ้า slow == fast: ถ้า slow == next(slow) break (cycle ยาว 1) มิฉะนั้นคืนค่า true
   • Mark visited: ตั้งค่า nums[...] = 0 ตามเส้นทางจาก i
4. คืนค่า false

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int next(vector<int>& nums, int i) {
        int n = nums.size();
        return (n + nums[i] + i) % n;
    }
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        for (int i = 0; i < n; i++) nums[i] %= n;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            while (nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0) {
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
                if (slow == fast) {
                    if (slow == next(nums, slow)) break;
                    return true;
                }
            }
            int x = nums[i];
            slow = i;
            while (nums[slow] * x > 0) {
                int temp = next(nums, slow);
                nums[slow] = 0;
                slow = temp;
            }
        }
        return false;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [2,-1,1,2,2]

Output: 1 (true)