c# - 从数组中取出两个数，使和为常数

Question

我遇到一道算法题。假设我收到一笔信用额度并且想从本地商店购买两件商品。我想购买两件加起来等于信用额度全部值(value)的元素。输入数据有三行。

第一行是信用额度，第二行是商品总金额，第三行是所有商品的价格。

示例数据 1:

200
7
150 24 79 50 88 345 3

这意味着我有 200 美元可以购买两件商品，共有 7 件商品。我应该以 200=150+50

的价格购买商品 1 和商品 4

示例数据 2:

8
8
2 1 9 4 4 56 90 3

这表示我有 8 美元可以从总共 8 篇文章中挑选两项。答案是第 4 项和第 5 项，因为 8=4+4

我的想法当然是首先创建数组，然后拿起任何项目，比如项目 x。创建另一个数组说“保留”，它从原始数组中删除 x。

用credit减去x的价格得到remnant，检查“remain”是否包含remnant。

这是我的 C# 代码。

        // Read lines from input file and create array price
        foreach (string s in price)
        {
            int x = Int32.Parse(s);
            string y = (credit - x).ToString();

            index1 = Array.IndexOf(price, s) ;
            index2 = Array.IndexOf(price, y) ;
            remain = price.ToList();
            remain.RemoveAt(index1);//remove an element
            if (remain.Contains(y))
            {
                break;
            }
        }
        // return something....

我的两个问题:

1. 复杂度如何？我认为是 O(n2)。
2. 算法有何改进？当我使用示例 2 时，我无法获得正确的索引。因为数组中有两个“4”，所以它总是返回第一个索引，因为 IndexOf(String) 报告此实例中指定字符串第一次出现的从零开始的索引。

Answer 1

您可以简单地在 O(nlogn) 时间内对数组进行排序。然后对每个元素 A[i] 在 O(nlogn) 时间内再次对 S-A[i] 进行二进制搜索。

编辑:正如 Heuster 所指出的，您可以通过使用两个指针(一个从开头，另一个从结尾)在线性时间内解决排序数组的 2-SUM 问题。