Finding the minimum distance between any pair of equal elements in an array

Given some array of integers A = [a₀, a₁, ..., a_n], find the minimum distance between a_i and a_j such that a_i = a_j and i != j (or indicate that no such indices exist).

So I've implemented a naive O(n²) approach in C++, involving iterating through the array looking for equal elements and updating the minimum distance appropriately:

#include <vector>
#include <climits>
#include <algorithm>

int MinPair(const std::vector<int>& nums)
{
    int ret = std::numeric_limits<int>::max();
    for(int i = 0; i != nums.size(); ++i)
    { 
        for(int j = 0; j != i; ++j)
        { 
            if(nums[i] == nums[j])  
                ret = std::min(ret, i - j);
        }
    }

    if(ret == std::numeric_limits<int>::max()) 
        return -1;

    return ret;
}

This works well, but I was told that a more "efficient" implementation exists involving std::map, without much clarification on what is more efficient. Namely, one could walk through the input array and store the first occurrence of an element within a map, and for every subsequent occurrence find the distance between that occurrence and the first index of that element in the map. If that distance is less than the current minimum, then we update that minimum.

However, I fail to see in what way this is more "efficient." Time complexity-wise, you would still have to walk through the input array (O(n)), and using std::map::find to identify whether or not an element is the first occurrence or not is also O(n), giving a total complexity of O(n²). Space complexity-wise you have to store a map in addition to the array/vector. What exactly am I missing here?

EDIT: I incorrectly assumed map::find was O(n); insertion and find operations are in fact O(log n), which one can immediately see even assuming basic implementations using something like binary search.