在c中找到兩個sum函數＃

Question

我想解決testdome在線考試中的一個問題。

問題是編寫一個函數，給定一個列表和一個目標總和，返回總和等於目標總和的任意兩個不同元素的從零開始的索引。如果沒有這樣的元素，該函數應該返回null。

這裏是我的代碼，它只是75％的真和25％的時間超過

using System; 
using System.Linq; 
using System.Collections.Generic; 

class TwoSum 
{ 
    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
    { 
     var result = from n1 in list 
        from n2 in list 
        where n1 + n2 == sum 
        select new Tuple<int, int>(list.IndexOf(n1), list.IndexOf(n2)); 
     return result.FirstOrDefault(); 
    } 
    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); 
    } 
} 

您可以複製粘貼我在在線網站的代碼，看看結果。 任何人都可以幫助我，所以我們得到100％的真實。 ：d

https://www.testdome.com/Questions/Csharp/TwoSum/4318

Answer 1

這是那些需要從不同的方法來在有問題的個案之一。而不是對所有值進行交叉連接並找到匹配的第一個和，而不是對所有值進行查找並循環並檢查當前項和總和的差值是否在該查找中。這樣你會得到線性性能的最壞情況，而不是多項式。

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    var lookup = list.Select((x, i) => new { Index = i, Value = x }) 
        .ToLookup(x => x.Value, x => x.Index); 
    for (int i = 0; i < list.Count; i++) 
    { 
     int diff = sum - list[i]; 
     if (lookup.Contains(diff)) 
      return Tuple.Create(i, lookup[diff].First()); 
    } 

    return null; 
} 

Answer 2

對您的版本稍作修改也會通過測試。但它不是100％正確的。這就告訴你Testdome上的測試用例不完整。我將把它作爲一個練習來解釋什麼是錯誤的。

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
    { 
     var result = from n1 in list 
        join n2 in list 
        on n1 equals sum - n2 
        select new Tuple<int, int>(list.IndexOf(n1), list.IndexOf(n2)); 
     return result.FirstOrDefault(x=>x.Item1!=x.Item2); 
    } 

Answer 3

使用juharr代碼

public static Tuple<int, int> FindTwoSumImprovedNonLinq(IList<int> list, int sum) 
    {   
     for (int i = 0; i < list.Count; i++) 
     { 
      int diff = sum - list[i]; 
      if (list.IndexOf(diff) > -1) 
       return Tuple.Create(i, list.IndexOf(diff)); 
     } 

     return null; 
    } 

Answer 4

輕微的修改版本代碼中的非LINQ的擴展方法通過使用一個HashSet，而不是查找。

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    var hs = new HashSet<int>(); 
    list.ToList().ForEach(x => hs.Add(x)); 

    for (int i = 0; i < hs.Count; i++) 
    { 
     var diff = sum - list[i]; 
     if (hs.Contains(diff)) 
     { 
      var index = list.IndexOf(diff); 
      return new Tuple<int, int>(i, index); 
     } 
    } 

    return null; 
} 

我曾嘗試和測試，並獲得100％的，即通過了所有測試，包括測試

Answer 5

一個更簡單的方式 「與大量元素的性能測試」是：

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    for (int i = 0; i < list.Count; i++) 
    { 
     // subtract the item to the sum to find the difference 
     int diff = sum - list[i]; 

     // if that number exist in that list find its index 
     if (list.Contains(diff)) 
     { 
      return Tuple.Create(i, list.IndexOf(diff)); 
     } 
    } 

    return null; 
} 

這樣你就不需要預先查找整個列表，但它仍然是75％。

Answer 6

公共靜態元組FindTwoSum（IList的列表，INT總和） {

 for(int i=0;i<list.Count;i++) 
     { 
      for(int j=0;j<list.Count;j++) 
      { 
       if((list[i]+list[j])==12) 
       { 
        return new Tuple<int, int>(i,j); 
       } 
      } 
     } 

     return null; 

}

這將工作

Answer 7

從與Atif的解決方案一點點修改，我們不需要首先將該列表複製到HashSet。

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    HashSet<int> hs = new HashSet<int>(); 
    for (int i = 0; i < list.Count; i++) 
    { 
     var needed = sum - list[i]; 
     if (hs.Contains(needed)) 
     { 
      return Tuple.Create(list.IndexOf(needed), i); 
     } 
     hs.Add(list[i]);     
    } 
    return null; 
} 

Answer 8

int[] arr = new int[] { 1, 0, 2, 3, 4, 3 }; 

    for (int i = 0; i < arr.Length; i++) 
    { 
     var requiredElements = arr.Select((item, index) => new { index, item }).Where(ind => ind.item.Equals(4 - arr[i])).ToList(); 

     if (requiredElements.Count > 0) 
     { 
      foreach (var disp in requiredElements) 

       Console.WriteLine("Indexes are " + i.ToString() + ":" + disp.index); 
     } 
     break; 
    } 

} 

//其中4是目標進 - ind.item.Equals（4 - ARR [I]）