Ниже два метода возвращают правильные результаты, но не с тестом производительности

Question

Я пишу этот метод и пытался написать его двумя способами, но этот метод не прошел тест производительности.

Метод Проблема: Напишите функцию, которая при получении списка и целевой суммы возвращаетэффективно по отношению к используемому времени два различных индекса на основе нуля любых двух чисел, сумма которых равна целевой сумме. Если нет двух чисел, функция должна вернуть ноль.

Например, FindTwoSum (new List () {3, 1, 5, 7, 5, 9}, 10) должен вернуть Tuple, содержащий любойиз следующих пар индексов:

• 0 и 3 (или 3 и 0) как 3 + 7 = 10
• 1 и 5 (или 5 и 1) как 1 + 9= 10

• 2 и 4 (или 4 и 2) при 5 + 5 = 10

  using System;
  using System.Collections.Generic;
  using System.Linq;
  class TwoSum
  {
  public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
  {
      int? item1Index = null;
      int? item2Index = null;
  
      var len = list.Count;
      int i = 0;
      while (i < len)
      {
          var j = i + 1;
          while (j < len)
          {
              if ((list[i] + list[j]).Equals(sum))
              {
                  item1Index = i;
                  item2Index = j;
                  break;
              }
              j++;
          }
          i++;
      }
      if (item1Index.HasValue && item2Index.HasValue)
          return new Tuple<int, int>(item1Index.Value, item2Index.Value);
  
      return null;
  }
  
  public static Tuple<int, int> FindTwoSum2(IList<int> list, int sum)
  {
      int? item1Index = null;
      int? item2Index = null;
  
  
      var result = (from list1 in list.Select((i,idx)=> new { item= i, index = idx})
                    from list2 in list.Select((i, idx) => new { item = i, index = idx })
                    select new
                    {
                        ListOneItem = list1.item,
                        ListOneItemIndex = list1.index,
                        ListTwoItem = list2.item,
                        ListTwoItemIndex = list2.index
                    }).Where(c => c.ListOneItemIndex != c.ListTwoItemIndex 
                                  && (c.ListOneItem + c.ListTwoItem).Equals(sum))
  
                      .FirstOrDefault();
      if (result != null)
          return new Tuple<int, int>(result.ListOneItemIndex, result.ListTwoItemIndex);
      return null;       
  }
  
  public static void Main(string[] args)
  {
      Tuple<int, int> indices = FindTwoSum(new List<int>() { 3, 1, 5, 7, 5, 9 }, 10);
      if (indices != null)
      {
          Console.WriteLine(indices.Item1 + " " + indices.Item2);
      }
  }  
  }
  

Answer 1

Вместо break из внутреннего while вы должны return, в противном случае код оценивает все комбинации через внешний цикл while.

Кроме того, вы можете следовать приведенному ниже оптимальному подходу, который использует словарный подход для оценки суммы за один проход (в одном цикле while).

Подробная информация о коде:

• Приведенная ниже программа поддерживает быстрый поиск с использованием Dictionary.
• Список повторяется и вставляет элементы в словарь. Кроме того, можно проверить, существует ли дополнение текущего элемента в Словаре. I

• Программа проверяет, существует ли дополнение каждого элемента (target - nums [i]) в Dictionary. Если он существует, то это решение и немедленно его вернуть.

  public static Tuple<int, int> FindTwoSum(int[] nums, int target) {
    Dictionary<int, int> hashData = new Dictionary<int, int>();
    for (int index = 0; index < nums.Length; index++)
    {
      int remainingTarget = target - nums[index];
      if (hashData.ContainsKey(remainingTarget))
      {
          return new Tuple<int, int>(hashData[remainingTarget], index);
      }
      else
      {
          if (!hashData.ContainsKey(nums[index]))
          {
              hashData.Add(nums[index], index);
          }
       }
   }
  
    return null;
  }
  

Поскольку каждый элемент списка просматривается только один раз, поэтому временная сложность этой программы равна O(n). Каждый просмотр таблицы стоит всего O (1) O (1) раз.