Leetcode наносит ответный удар. Поиск дубликатов. Делаем из Easy Hard.

В общем-то, задача как задача. 217. Contains Duplicates. Отмечена Easy.
https://leetcode.com/problems/contains-duplicate/

Вернуть true, если список содержит дубликаты, и false, если все элементы уникальны. До 100 тысяч элементов в диапазоне 32-битного знакового целого числа.

Тут даже аудитория видеокурсов знает, что надо сделать set, запихать в него элементы и сравнить его длину с длиной массива. Только самые дремучие будут бегать по массиву двойным циклом за O(n²), впрочем, сэкономив при этом изрядно памяти.

Думал, сейчас за пару минут решу и дальше пойду. Но что-то пошло не по плану.

 class Solution {

public:

    bool containsDuplicate(vector& nums) {

        unordered_set nset;

        nset.reserve(nums.size() / 2);

        for (const auto n : nums) {

            if (nset.contains(n)) return true;

            nset.insert(n);

        }

        return false;

    }

}; 

Я разве не зарезервировал место, предотвращая частую реаллокацию с перемещением элементов? Разве тут нет раннего выхода по первому дубликату? Что в этом коде вообще лишнее?

Вспомнился розыгрыш с какого-то радио 20-летней давности, где крутили 4 вопроса:
1) Это же hash set?
2) У него ведь линейная сложность?
3) А почему я тогда получаю такие результаты?4) А кто может ответить на этот вопрос?
И дальше - к п. 1.

Заметим, это была лучшая из 6 попыток, остальные доходили до 112ms и 65%.

И, наконец, переходим к вопросу.
Как это нужно решать, чтобы получить хотя бы вот такой результат?
Т.е. время выполнения снижено почти вдвое, а футпринт памяти - на 10 мегов.
Смотрел солюшены, люди не понимают разницы между std::set и std::unordered_set, а большинство бегает по массиву теми самыми циклами за O(n²).

Сразу скажу, что коварство литкода в тестовых данных этой "лёгкой" задачи превосходит даже их обычные традиции. Есть кейсы с очень длинными списками. Есть кейсы с данными, специально подобранными для максимизации коллизий в STL hash set, например, отличающимися на один бит в средних разрядах (так обходят внутреннее дополнительное хеширование старших разрядов в младшие). Естественно, как и во всех прочих тестах, присутствуют INT_MIN, INT_MAX, так что надеяться на ограниченность диапазона элементов не стоит.

 class Solution { 

public: 

    bool containsDuplicate(vector& nums) { 

        sort(nums.begin(), nums.end()); 

        return adjacent_find(nums.begin(), nums.end()) != nums.end(); 

    } 

}; 

 lass Solution { 

public: 

    static vector num; 

    bool containsDuplicate(vector& nums) 

    { 

        bool res = false; 

        for (auto& i : nums)  

        { 

            if (num[i + 1000000000]) {res = true; break;} else num[i + 1000000000] = true; 

        } 

        for (auto&i:nums) num[i + 1000000000] = false; 

        return res; 

    } 

}; 

vector Solution::num = vector(2000000001); 

 auto init = []()

{ ios::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);

  return 'c';

}(); 

 ```cpp  

 

for (const auto n : nums) {  

 

    if (nset.count(n)) {  

 

        return true;  

 

    }  

 

    nset.insert(n);  

 

}  

 

```