<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        switch (nums.size()) {
        case 0:
            return false;
        case 1:
            return false;
        case 2:
            return nums.front() == nums.back();
        }
        auto const begin = nums.begin();
        auto const end = nums.end();
        for (auto cursor = begin + 1; cursor != end; cursor += 1) {
            if (SortCursor(begin, cursor))
                return true;
        }
        return false;
    }

private:
    bool SortCursor(auto begin, auto cursor) const {
        auto sortedEnd = cursor - 1;
        if (*sortedEnd == *cursor)
            return true;
        if (*sortedEnd < *cursor)
            return false;
        auto insertionPoint = (*begin > *cursor)
                                  ? begin
                                  : std::lower_bound(begin, cursor, *cursor);
        if (*insertionPoint == *cursor)
            return true;
        std::rotate(insertionPoint, cursor, cursor + 1);
        return false;
    }
};
59703