Finding pair in an array with the OO approach
The biggest problem here IMO is that, from a OOP point of view, it's a bit difficult to represent an algorithm as an object. Objects usually represent &quot;things&quot; which have methods that represent &quot;actions&quot; that happen to those things. Algorithms are usually used in such actions. The object in this case would be the array, but since in Java arrays aren't objects and Java doesn't have the concept of extension methods, it's difficult to represent a stand-alone algorithm in an OOP way.
EDIT: I just realized, your algorithms are returning a pair of indices instead of values from the arrays. That doesn't correspond to the example, and in most cases the pair of values would be more useful than the indices. Also my remarks are based on the assumption that values are returned.
Never-the-less here are some remarks about the OOP side of things:
class Pair
The biggest problem here is the usage of -1 to represent ... what exactly? Keep in mind -1 is  a completely &quot;normal&quot; valid integer. A developer who uses that class and who doesn't explicitly check for that -1 will get no error message when using it in calculations and instead his program most likely will run fine, but display wrong results. More importantly your program currently displays &quot;(-1, -1)&quot; when there is no solution, but it looks like a possible solution. What if the array contains two -1s and you ask for a sum of -2? How do you distinguish between a correct result and no result.
If you actually should need such an &quot;empty&quot; value of Pair you should use Integers and null. However in your case there is no need for such an empty result. Just drop the default constructor. Instead just have your algorithm return null or - if you don't like using null - use Java 8's Optional.
Pair is a perfect case for an immutable object. There is no reason to change one of the values in the pair after creation. Make the fields private and create getters for them.

PairSum/PairSumFast
Since both classes do the same thing, it would be worth considering have them implement a common interface. For such a small example it may be over-engineered, but it would display some insight into OOP.
Another thing that would show a bit more OOP would be to use the Collection interface instead of an array to provide the input. In Java it is rare to actually use an array as a &quot;top level&quot; data structure, since they are not objects are inflexble and don't fit in with Java's collection infrastructure. Arrays are usually used as a low level data storage structure and hidden in the implementation details of classes.