Given a sum of two elements in an int array, how to find their smallest indexes?-CodePudding

I want to return an array of 2 integers, containing the indexes of a pair of integers in the array whose sum is k.

int[] numbers = new int[]{1, 5, 8, 1, 2};
int k = 13;

I have done this method :

public int[] findSumPair(int[] numbers, int k){
   
    int[] pairs = new int[2];

    for(int i = 0; i < numbers.length; i  ){
        for(int j = i   1; j < numbers.length; j  ){
            if (numbers[i]   numbers[j] == k){
                pairs = new int[]{i, j};

               if (numbers[i]   numbers[j] != k){
                   pairs = new int[]{0, 0};
               }
            }
        }
    }
    return pairs;
}

With previous array and sum it works & returns:

[1,2]

For example with this:

int[] numbers = new int[]{1, 5, 0, 1, 2, 7, 8, 6};
int k = 13;

I should have:

[1,6] // But I get [5,7]

How can I, in case there are several possible pairs whose sum is equal to the target, return the pair with the lowest left index?

And in the case of 2 pairs with the same left index, go for the pair with the lowest right index?

Many thanks in advance

CodePudding user response：

Since you are scanning left to right, you can just return after finding the first match i.e., replacing

           if (numbers[i]   numbers[j] != k){
               pairs = new int[]{0, 0};
           }

with return pairs.

CodePudding user response：

Assume a return of [n,m] is an valid output where n<>m and m > 0. Assume a return of [0,0] is an exception output indicates the pair is not found.

There are some mistake in your function:

    public int[] findSumPair(int[] numbers, int k) {

        int[] pairs = new int[2];

        for (int i = 0; i < numbers.length; i  ) {
            for (int j = i   1; j < numbers.length; j  ) {
                if (numbers[i]   numbers[j] == k) {
                    // if a pair is found, you could stop looking anymore
                    pairs = new int[] { i, j };

                    // unreachable statement
                    if (numbers[i]   numbers[j] != k) {
                        pairs = new int[] { 0, 0 };
                    }
                }
            }
        }
        return pairs;
    }

Firstly, if you want to find the smallest index, once you found a matched pair, you could break the for-loop. Since you start searching from the left, the first match must be the smallest. No matter now hard the program try, the next result is not the smallest.

Secondly, I think you try to set a false case condition to return [0,0] if no pair is found. However, the condition is contradict to its outer if condition. That is a unreachable statement. You can put that at the very end of the function since when we reach that part, the searching is already completed. I modified the function as:

    public int[] findSumPair(int[] numbers, int k) {

        for (int i = 0; i < numbers.length; i  ) {
            for (int j = i   1; j < numbers.length; j  ) {
                if (numbers[i]   numbers[j] == k) {
                    // quit immediately
                    return new int[] { i, j };
                }
            }
        }
        // if we reach here, no pair is found
        return new int[2];
    }

the main()

        int[] result = main.findSumPair(new int[] { 1, 5, 8, 1, 2 }, 13);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 5, 0, 1, 2, 7, 8, 6 }, 13);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 2, 2, 2, 1 }, 2);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 2, 2, 4, 3 }, 7);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 3, 9, 9, 9, 4 }, 5);
        System.out.println(Arrays.toString(result));

console output

[1, 2]
[5, 7]
[0, 5]
[4, 5]
[0, 6]

CodePudding user response：

@bui

I have to keep this part:

if (numbers[i]   numbers[j] != k) {
    pairs = new int[]{0, 0};
}

Because:

[0, 0]

Must be returned if no pair equal to k is found