算法通過詞典搜索

林從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得到：

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); 
       } 
      }

這將返回我的代碼正確的答案，但在失敗3出4例quesitong因爲：

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.

因此，即時通訊使用嵌套循環，但林猜測在這個實例中，以傳遞提示2我需要使用字典...我怎樣才能重構這到使用字典？感謝您的幫助！

來源

2017-09-24 John

您直接找到一對，其中sum是所需的總和。你應該創建一個臨時集合並添加對，並在那些'foreach'之後返回所述集合。 – Vivick

如果你的集合是有序的，你可以從內部向內搜索，而不是匹配所有對象......但這是一個很大的if :) – Noctis

你的問題很難閱讀。您可以用引號替換代碼段，以防引用某些內容。 –

你沒有返回索引，你正在返回值。 for循環不是foreach循環。

嵌套的for循環的解決辦法是這樣的：

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;

我會留下，爲您打造的字典解決方案。

來源

2017-09-24 05:42:26

算法通過詞典搜索

回答

相關問題