Reversing the vowels in a String
Time complexity is \$O(n)\$ indeed. Since every input character must be inspected, this asymptotic is impossible to improve. However, it is possible to improve the constant. See below.
Space complexity is \$O(n)\$ indeed. However, it is possible to solve the problem is \$O(1)\$. Consider two iterators, one running left to right, and another running right to left. As long as the first iterator points a consonant, print it. As soon as it hits a vowel, scan the second iterator (right to left) until it finds a vowel, and print that vowel. Notice that this approach also doesn't need values and keys - and hence doesn't need to build them. This is how time complexity is also improved.
The line

sb.replace(num.intValue(),num.intValue() + 1,String.valueOf(values.get(count)));


is very hard to read. It is even harder to prove that it works correctly.