std::distance in std::unordered_set

Question

I wanted to solve the problem "TwoSum" with the help of the HashSet. When I try to post the solution, it fails in the second case with the answer [2,0]

However, when I try to do the same thing шт IDE it returns me the right answer

Code:

std::vector<int> twoSum(std::vector<int>& nums, int target) 
    {
        std::unordered_set<int> mp;
        for (auto i = 0; i < nums.size(); ++i) 
        {
            if (auto it = mp.find(target - nums[i]); it == mp.end()) 
            {
            mp.emplace(nums[i]);
            }
            else 
            {
                return {static_cast<int>(std::distance(mp.begin(), it)), i };
            }
        }
    return {};
    }

Answer 1

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
}

This comes from Leetcode China ，Official Explanation

Answer 2

From the doc:

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value.

This means that the order of elements stored in std::unordered_set is not guaranteed to be the same as insertion order! So you can't expect that std::distance gives you the index of element in the original array.

To keep access to indices of values you can use std::unorderd_map:

std::vector<int> twoSum(std::vector<int>& nums, int target)
{
    std::unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); ++i)
    {

        if (auto it = mp.find(target - nums[i]); it == mp.end())
        {
            mp[nums[i]] = i;
        }
        else
        {
            return {it->second, i};
        }
    }
    return {};
}

Answer 3

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

Link：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/