LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 题目要求 O(1) 空间，因此不能用哈希表。将 i 与 nums[i] 视为链表的相邻节点，如果 nums[i] 存在重复元素，则该链表有环

nums[i] = 1 3 4 2 2
i       = 0 1 2 3 4

nums[0] = 1
nums[1] = 3
nums[3] = 2
nums[2] = 4
nums[4] = 2
nums[2] = 4
nums[4] = 2
陷入循环

• 用快慢指针找环入口即可

class Solution {
 public:
  int findDuplicate(vector<int>& nums) {
    int slow = 0;
    int fast = 0;
    while (true) {
      slow = nums[slow];
      fast = nums[nums[fast]];
      if (slow == fast) {
        break;
      }
    }
    fast = 0;
    while (slow != fast) {  // 找环入口
      slow = nums[slow];
      fast = nums[fast];
    }
    return slow;
  }
};