C#中两个整数元组的总和

Question

我正在尝试解决这个问题,就像为求职面试做准备一样:编写一个函数,给定一个列表和一个目标总和,返回任何两个不同元素的从零开始的索引,其总和等于目标总和.如果没有这样的元素,则该函数应返回null.

例如,FindTwoSum(new List(){1,3,5,7,9},12)应该返回以下任何索引元组:

1,4(3 + 9 = 12)

2,3(5 + 7 = 12)

3,2(7 + 5 = 12)

4,1(9 + 3 = 12)

这是我到目前为止所做的

public static Tuple<int, int> FindTwoSum(List<int> list, int sum)
    {
        List<Tuple<int, int>> ListOfInt = new List<Tuple<int, int>>();
        for (int i=0; i<list.Count; i++)
        {
            for(int j=0; j<list.Count; j++)
            {
                if (list[i] + list[j] == sum)
                {
                    ListOfInt.Add(new Tuple<int, int>(i,j));
                }
            }
        }

        foreach ( var elemt in ListOfInt)
        {
            return elemt;
        }
        return null;

    }

问题是找到所有结果并保存在元组中:但我仍然无法将结果打印到控制台.我认为这foreach句话有些不对劲.在我编写的主要方法中,将结果打印到控制台:

Console.WriteLine(FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12));

请问任何建议:)？

Answer 1

那么,如果a + b = sum那时b + a = sum,你可以切断内环并立即返回两对 ; 您当前实现的另一个问题和反例是a + a = sum不计算,例如

  {3, 6, 9}, 12

应该只返回

  0, 2 // 3 + 9
  2, 0 // 9 + 3

并不是

  1, 1 // 6 + 6 is wrong

我宁愿实现返回的解决方案IEnumerable<Tuple<int, int>>:

  // Are you given List<int>? What about int[]? IEnumerable<int> is a much better choice 
  public static IEnumerable<Tuple<int, int>> FindTwoSum(IEnumerable<int> items, int sum) {
    // Validate Arguments (the method is public one!)
    if (null == items)
      throw new ArgumentNullException("items");

    var list = items.ToList();

    for (int i = 0; i < list.Count - 1; ++i)   // last line doesn't count
      for (int j = i + 1; j < list.Count; ++j) // note j = i + 1
        // if ((list[i] + list[j] == sum) && (list[i] != list[j])) { // distinct values and indexes
        if (list[i] + list[j] == sum) { // distinct indexes only
          yield return new Tuple<int, int>(i, j);
          yield return new Tuple<int, int>(j, i);                
        }
  }

如果你想要不同的值以及不同的索引而不是

  if (list[i] + list[j] == sum)

应该

  if ((list[i] + list[j] == sum) && (list[i] != list[j]))

不同的值,但不是索引不是一种情况,因为a[i] == a[i]每当索引不区分值时.我们有条件

  if ((list[i] + list[j] == sum) && (list[i] != list[j]))

测试:

  // note that I can pass an array (int[]) or list (List<int>) whatever collection
  String report = String.Join(Environment.NewLine, 
    FindTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12));

  // (1, 4)
  // (4, 1)
  // (2, 3)
  // (3, 2)
  Console.Write(report);