通过字典搜索算法

Question

im从q https://www.testdome.com/for-developers/solve-question/10282

Write a function that, given a list and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return null.
For example, FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12) should return a Tuple<int, int> containing any of the following pairs of indices:
1 and 4 (3 + 9 = 12)
2 and 3 (5 + 7 = 12)
3 and 2 (7 + 5 = 12)
4 and 1 (9 + 3 = 12)

到目前为止iv GoT：

 class TwoSum
           {
               public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
               {
                   //throw new NotImplementedException("Waiting to be implemented.");
                   IList<int> duplicateList = list;
                   foreach (int i in list)
                   {
                       foreach (int j in duplicateList)
                       {
                           if (i != j)
                           {
                               if (i + j == sum)
                               {
                                   return Tuple.Create(i, j);
                               }
                           }
                       }
                   }
                   return null;
               }
               public static void Main(string[] args)
               {
                   Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);
                   Console.WriteLine(indices.Item1 + " " + indices.Item2);
               }
           }

这在我的代码中返回正确的答案，但在Quesitong中的4个情况中有3个失败，因为：

Example case: Wrong answer 
  No solution: Correct answer 
  One solution: Wrong answer 
  Performance test with a large number of elements: Wrong answer 

我看着提示

    Hint 1: Nested for loops can iterate over the list and calculate a sum in O(N^2) time.
Hint 2: A dictionary can be used to store pre-calculated values, this may allow a solution with O(N) complexity.

所以我使用嵌套循环，但是我在这种情况下猜测以通过hint2，我需要使用字典...如何将其重构为使用字典？感谢您的帮助！

Answer 1

您没有返回索引，而是返回值。for循环不是foreach循环。

嵌套用于环的解决方案将是这样的：

for(int i=0; i<list.Count-1; i++)
{
    for(int j=i+1;j<list.Count;j++)
    {
        if(list[i]+list[j] == sum)
        {
            return Tuple.Create(i, j);
        }
    }
}
return null;

我将离开字典解决方案供您创建。

Answer 2

嗨，这个收到50％

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
{
        int n = list.Count-1;
        while(n != 0)
        {
            for (int i = 0; i <= list.Count-1 ; i++)
            {
                if (list[n] + list[i] == sum)
                {
                    return Tuple.Create(i, n);
                }
            }
            n--;
        }
        return null;
}

//获取列表值：

        var aat = (from l1 in list
                  from l2 in list
                  where l1 + l2 == 12
                  group new { l1, l2} by new { l1, l2 } into gp
                  select new {gp.Key}).ToDictionary( a => a.Key.l1, b => b.Key.l2 );

//获取值的列表索引：

        var aav = (from l1 in list
                   from l2 in list
                   where l1 + l2 == 12
                   group new { l1, l2 } by new { l1, l2 } into gp
                   select new { gp.Key })
                   .ToDictionary( a => list.IndexOf(a.Key.l1), b => list.IndexOf(b.Key.l2) 
                   );