在数组中查找两个商品的索引，这两个商品的价格加起来就是一个值

Question

我正在尝试解决谷歌代码堵塞的问题。

问题

您在当地商店获得信用积分，并想购买两件商品。您首先穿过商店，创建一个所有可用商品的列表L。从这个列表中，您想购买两件商品，它们加起来等于信用积分的全部价值。您提供的解决方案将由两个整数组成，指示列表中商品的位置（首先是较小的数字）。

输入

输入的第一行给出了案例的数量，接着是N. N个测试案例。对于每个测试案例，将有:

一行包含C值，这是你在商店的信用额度。一行包含值I，即商店中的商品数量。包含用空格分隔的I个整数列表的一行。每个整数P表示商店中一件商品的价格。每个测试用例都有一个解决方案。输出

对于每个测试用例，输出一行包含“Case #x:”的内容，后跟两个商品的索引，这两个商品的价格加起来就是商店信用。应该首先输出较低的索引。

到目前为止，我这样做了。然而，当我将100,3,5,75,25作为输入时，我得到1,22,1作为输出，因为它第二次遍历数组。我如何得到1,2作为输出？

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int credit = in.nextInt();

        int number = in.nextInt();

        int[] items = new int[number];
        for (int i = 0; i < number; i++){
            items[i] = in.nextInt();
        }

        for (int i = 0; i < number; i++){
            for (int j = 0; j < number; j++){
                if (items[i] + items[j] == credit){
                    System.out.print(i + "," + j + " ");
                }
            }
        }
    }
}

Answer 1

您可以使用排序方法以及二叉搜索来使其成为更快的解决方案。例如：

假设输入价格为“100、3、5、75、25”

1)使用快速排序对此价目表进行排序。列表将变成(3，5，25，75，100)

2） 对每个项目使用二进制搜索来找到解决方案。

Answer 2

您应该让内部循环仅从j=i1开始：

for (int i = 0; i < number - 1; i++){
     for (int j = i + 1; j < number; j++){
          if (items[i] + items[j] == credit){
               System.out.print(i + "," + j + " ");
          }
     }
}