我遇到了一个算法问题。假设我收到一张信用卡，只想从当地商店买两件。我想买两件商品，加起来就是信用证的全部价值。输入数据有三行。
第一行是信用，第二行是项目的总额，第三行列出了所有项目的价格。
样本数据1:
200
7
150 24 79 50 88 345 3
这意味着我有200美元买两件东西，一共有7件。我应该购买物品1和物品4作为200=150+50
样本数据2:
8
8
2 1 9 4 4 56 90 3
这表明我有8美元可以从总共8篇文章中挑选两件。答案是第4项和第5项，因为8=4+4
我的想法是首先创建数组，然后选择任何项目，比如项目x。创建另一个数组，比如"保留"，从原始数组中删除x。
从信用中减去x的价格，得到剩余部分，并检查"剩余部分"是否包含剩余部分。
这是我的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....
我的两个问题：
- 复杂性如何？我认为它是O(n2)
- 算法有什么改进吗？当我使用示例2时，我很难获得正确的索引。因为数组中有两个"4"，所以它总是返回第一个索引，因为IndexOf(String)报告了该实例中指定字符串第一次出现的从零开始的索引
您可以简单地按O(nlogn)时间对数组进行排序。然后对于每个元素A[i]在O(nlogn)时间内再次对S-A[i]进行二进制搜索。
编辑：正如Heuster所指出的，您可以通过使用两个指针(一个从开始，另一个从结束)在线性时间内解决排序数组上的2-SUM问题。
创建价格的HashSet<int>。然后按顺序浏览。类似于：
HashSet<int> items = new HashSet<int>(itemsList);
int price1 = -1;
int price2 = -1;
foreach (int price in items)
{
int otherPrice = 200 - price;
if (items.Contains(otherPrice))
{
// found a match.
price1 = price;
price2 = otherPrice;
break;
}
}
if (price2 != -1)
{
// found a match.
// price1 and price2 contain the values that add up to your target.
// now remove the items from the HashSet
items.Remove(price1);
items.Remove(price2);
}
这是创建HashSet的O(n)。因为HashSet中的查找是O(1)，所以foreach循环是O(n)。
这个问题被称为2-sum。看见例如http://coderevisited.com/2-sum-problem/
这里有一个在O(N)时间复杂度和O(N)空间中的算法：-
1. Put all numbers in hash table.
2. for each number Arr[i] find Sum - Arr[i] in hash table in O(1)
3. If found then (Arr[i],Sum-Arr[i]) are your pair that add up to Sum
注意：-只有当Arr[i]=Sum/2时，才能得到假阳性，但您可以始终检查O(N)中的数组中是否有两个Sum/2
我知道这是一年半后发布的，但我只是碰巧遇到了这个问题，想添加输入。
如果存在一个解决方案，那么您知道解决方案中的两个值都必须小于目标和。
-
在值数组中执行二进制搜索，搜索目标和(可能存在也可能不存在)。
-
二进制搜索将以找到和或小于和的最接近值结束。这是您在使用前面提到的解决方案搜索阵列时的起点高值。任何高于新的起点高值的值都不能出现在解决方案中，因为它超过了目标值。
- 此时，您已经在log(n)时间中消除了一块数据，否则这些数据将在O(n)时消除
同样，这是一个只有在数据集需要的情况下才值得实现的优化。