给定一个 int 数组中两个元素的总和，如何找到它们的最小索引？

Question

我想return一个2个整数的数组，包含数组中一对整数的索引其总和为k.

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

这个方法我做过:

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;
}

使用之前的数组并求和它有效 & returns:

[1,2]

例如：

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

我应该有：

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

如果有几个可能的对，其总和等于目标，我如何return具有最低左索引的对？

如果 2 对具有相同的左侧索引，则选择右侧索引最低的一对？

非常感谢

Answer 1

由于您是从左到右扫描，您可以在找到第一个匹配项后 return，即替换

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

与 return pairs.

Answer 2

@bui

我必须保留这部分：

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

因为：

[0, 0]

如果没有找到等于 k 的对，则必须返回

Answer 3

假设 [n,m] 的 return 是有效输出，其中 n<>m 且 m > 0。假设 [=34= [0,0] 的 ] 是异常输出，表示未找到该对。

你的函数有一些错误：

    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;
    }

首先，如果你想找到最小的索引，一旦找到匹配的对，你就可以打破for-loop。由于您从左侧开始搜索，因此第一个匹配项必须是最小的。不管现在程序怎么努力，下一个结果都不是最小的。

其次，如果没有找到对，我认为您尝试将 false case 条件设置为 return [0,0]。但是，该条件与其外部 if 条件相矛盾。那是一个遥不可及的声明。你可以把它放在函数的最后，因为当我们到达那个部分时，搜索已经完成。我将函数修改为：

    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];
    }

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));

控制台输出

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

给定一个 int 数组中两个元素的总和，如何找到它们的最小索引？

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

java

arrays

indexing

sum