Find pairs in an integer array whose sum == 10

Question

I'm practicing for technical interviews and I'm looking for ways to improve my answers/code. Please point out the flaws you see and how I can make this better.

Task: Find pairs in an integer array whose sum is equal to 10 (bonus: do it in linear time)

Pairs.java

 //Container class that will hold the indices of the pairs found
 public class Pairs<T,K> {
 private T tval;
 private K kval;
 public Pairs(){
 }
 public Pairs(T tv, K kv){
 this.tval = tv;
 this.kval = kv;
 }
 public T getFirst() {
 return tval;
 }
 public void setFirst(T tval) {
 this.tval = tval;
 }
 public K getSecond() {
 return kval;
 }
 public void setSecond(K kval) {
 this.kval = kval;
 }
 public void clear(){
 this.tval = null;
 this.kval = null;
 }
 }

EqualPairs.java

 import java.util.ArrayList;
 import Utilities.Pairs;
 /**
 * Find pairs in an integer array whose sum is equal to 10
 * (bonus: do it in linear time) 
 * 
 */
 public class EqualPairs {
 //O(n^2). First solution I came up with. Debugging through this
 //method actually gave me the idea on how to attempt to solve this
 //problem in linear time.
 public static ArrayList<Pairs> equal(int[] array){
 int numComparisons = 0; //for big O analysis
 ArrayList<Pairs> pairsList = new ArrayList<Pairs>();
 for(int i = 0;i<array.length;i++){
 for(int j=0;j<array.length;j++){
 if(array[i]+array[j]==10 && i!=j && i<j){
 Pairs pair = new Pairs(i,j);
 pairsList.add(pair); 
 }
 numComparisons++;
 }
 }
 log("Number of comparisons made for input of size "+array.length+": "+numComparisons);
 return pairsList;
 }
 public static void log(Object o){
 System.out.println(o);
 }
 //Asymptotic complexity unknown
 public static ArrayList<Pairs> equalInLinear(int[] array){
 int numComparisons = 0; //for big O Analysis
 ArrayList<Pairs> pairsList = new ArrayList<Pairs>();
 for(int i = 0;i<array.length;i++){
 //j=i+1 is the only difference between this method and
 //the previous one. 
 for(int j=i+1;j<array.length;j++){
 if(array[i]+array[j]==10 && i!=j && i<j){
 Pairs pair = new Pairs(i,j);
 pairsList.add(pair); 
 }
 numComparisons++;
 }
 }
 log("Number of comparisons made for input of size "+array.length+": "+numComparisons);
 return pairsList;
 }
 }

EqualPairsTest.java

 import static org.junit.Assert.*;
 import java.util.ArrayList;
 import org.junit.Test;
 import Utilities.Pairs;
 import junit.framework.TestCase;
 public class EqualPairsTest extends TestCase {
 @Test
 public void testEqualSimpleOne() {
 int[] arr1={1,9};
 ArrayList<Pairs> p =EqualPairs.equal(arr1);
 assertEquals(1,p.get(0).getSecond());
 assertEquals(0,p.get(0).getFirst());
 }
 public void testEqualSimpleTwo(){
 int[] arr={3,5,6,7,5,-1,11};
 ArrayList<Pairs> p = EqualPairs.equal(arr);
 assertEquals(0, p.get(0).getFirst()); 
 assertEquals(3,p.get(0).getSecond()); 
 assertEquals(1, p.get(1).getFirst()); 
 assertEquals(4, p.get(1).getSecond()); 
 assertEquals(5, p.get(2).getFirst()); 
 assertEquals(6, p.get(2).getSecond()); 
 }
 public void testEqualLinearSimple(){
 int[] arr1={1,9};
 ArrayList<Pairs> p =EqualPairs.equalInLinear(arr1);
 assertEquals(1,p.get(0).getSecond());
 assertEquals(0,p.get(0).getFirst());
 }
 public void testEqualInLinearSimpleTwo(){
 int[] arr={3,5,6,7,5,-1,11};
 ArrayList<Pairs> p = EqualPairs.equalInLinear(arr);
 assertEquals(0, p.get(0).getFirst()); 
 assertEquals(3,p.get(0).getSecond()); 
 assertEquals(1, p.get(1).getFirst()); 
 assertEquals(4, p.get(1).getSecond()); 
 assertEquals(5, p.get(2).getFirst()); 
 assertEquals(6, p.get(2).getSecond()); 
 }
 }

Answer 1

\$O(n^2)\,ドル not linear

The second algorithm is superior to the first, but is still an \$O(n^2)\$ algorithm. Furthermore, you have some redundant checks. This:

 if(array[i]+array[j]==10 && i!=j && i<j){

could be turned into this:

 if (array[i] + array[j] == 10) {

because j starts at i+1 so you know the last two conditions are always true.

Faster methods

One faster method would be to sort the array first. Then you can locate the pairs in linear time after that. This would be \$O(nlog(n))\$ total time. However, depending on how duplicates are handled, this could also degenerate to \$O(n^2)\$ time (for example an array of all 5's).

An even faster method would be to use a HashMap to store each value that you have seen so far. Then when you come across a new value such as 7, you use the HashMap to look up whether you have seen a 3 so far. If you have, then 7/3 is a valid pairing. This will run in \$O(n)\$ time if duplicates are not printed.

Keep in mind that if all duplicate pairs must be printed, no solution will do better than \$O(n^2)\,ドル because you will need to print every pair if the array consists of all 5's.