Java - how to stop nested loops from checking same indices twice?

Question

Given an array and a number N call a pair of numbers from the array a Perfect Pair if their sum is equal to N.

Find all of the perfect pairs and return the sum of their indices. Note that any element of the array can only be counted in one Perfect Pair.

Examples

pairwise([1, 4, 2, 3, 0, 5], 7) = 11 Since the Perfect Pairs are (4, 3) and (2, 5) with indices 1 + 3 + 2 + 5 = 11.

pairwise([1, 3, 2, 4], 4) = 1 Since the element at index 0 (i.e. 1) and the element at index 1 (i.e. 3) form the only Perfect Pair.

Input 1 (arr) → array.integer : array of non-negative integers

Input 2 (N) → integer : positive integer

Output → integer : sum of indices and 0 if no Perfect Pair exists

My Code:

     public static void main(String[] args) {
        int x[] = {1,4,2,3,0,5};
        System.out.println(pairwise(x, 7)); 
    }

     public static int pairwise(int[] arr, int N) {    
        int t=0;
        for(int i=0;i<arr.length;i++){
          for(int k=0;k<arr.length;k++){
            if(arr[i]+arr[k] == N){
              t+=i+k;
            } 
          }
        }
        return t;
     }

The problem is my code checks indices twice, like (0,1) and (1,0) are treated like different indices.

Answer 1

The simplest options is to not check these in the first place. I assume i == k is not valid so you don't want to check k < i either.

public static void main(String[] args) {
    int x[] = {1, 4, 2, 3, 0, 5};
    System.out.println(pairwise(x, 7));
}

public static int pairwise(int[] arr, int N) {
    int t = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int k = i + 1; k < arr.length; k++) {
            if (arr[i] + arr[k] == N) {
                t += i + k;
                arr[i] = arr[k] = Integer.MIN_VALUE; // don't use these again
                continue;
            }
        }
    }
    return t;
}

prints

11

This ensures you won't go over the same numbers twice.

Note: this is an O(n^2) approach, if you have more numbers you will want an O(n) approach which means using a set or map of numbers.

// O(n)
Map<Integer, Integer> intToIndex = new HashMap<>();
for(int i = 0; i < arr.length; i++)
    intToIndex.put(arr[i], i);

// O(n)
for(int i = 0; i < arr.length; i++) {
    int numberToLookFor = N - arr[i];
    Integer k = intToIndex.get(numberToLookFor);
    if (k != null) {
        assert arr[i] + arr[k] == N;
        // do something with i and k
    }
}