In fact your previous solution was O(N log N) for N = $pad*@nums because of the sort, not O(Nē) (or did I miss something)?

However your current solution stores some amount of data twice in a hash where pointer is sufficient because @nums is already sorted.