c# - testdome.com 中的 TwoSum 和 BinarySearchTree；如何解决警告消息 : Performance test?

Question

我正在尝试解决 testdome.com 中的 C# 编程问题，但我发现了有关性能的问题。如何解决？

二叉搜索树

using System;

public class Node
{
    public int Value { get; set; }

    public Node Left { get; set; }

    public Node Right { get; set; }

    public Node(int value, Node left, Node right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

public class BinarySearchTree
{
    public static bool Contains(Node root, int value)
    {
        Console.WriteLine("value=" + value);
        if(root == null)
            return false;
        else if(root.Value == value)
            return true;
        else if(root.Value != value)
        {
            return Contains(root.Left, value) | Contains(root.Right, value);
        }
        return false;
    }

    public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        Console.WriteLine(Contains(n2, 3));
    }
}

Performance test on a large tree: Memory limit exceeded

https://www.testdome.com/for-developers/solve-question/7482

双和

using System;
using System.Collections.Generic;

class TwoSum
{
    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
    {
        for(int ctr1=0; ctr1<list.Count; ctr1++)
        {
            for(int ctr2=0; ctr2<list.Count; ctr2++)
            {
                if ((ctr1 != ctr2) && (list[ctr1]+list[ctr2] == sum))
                    return new Tuple<int, int>(ctr1, ctr2);
            }
        }
        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);
    }
}

Performance test with a large number of elements: Time limit exceeded

https://www.testdome.com/for-developers/solve-question/8125

Answer 1

对于Binary search tree，testdome.com提供了提示“如果正在搜索的值小于该节点的值，则可以忽略右子树”。这将内存消耗减少了一半。

public static bool Contains(Node root, int value) {
    Console.WriteLine("value=" + value);
    if (root == null) {
        return false;
    }
    else if (value == root.Value) {
        return true; 
    } 
    else if (value < root.Value) {
        // Hint 2: If a value being searched for is smaller than the value of the node, 
        // then the right subtree can be ignored.
        return Contains(root.Left, value);
    }
    else {
        return Contains(root.Right, value);
    }
    return false;
}

对于 TwoSum，如果我们假设输入数组中的值是唯一的，我们可以使用字典按其值查找索引(在 O(1) 时间内)。这与提示“字典可用于存储预先计算的值，这可能允许复杂度为 O(N) 的解决方案。”

// Write a function that, when passed a list and a target sum, 
// returns, efficiently with respect to time used, 
// two distinct zero-based indices of any two of the numbers, 
// whose sum is equal to the target sum. 
// If there are no two numbers, the function should return null.
public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) {

    if (list.Count < 2) {
        return null;
    }
    
    // Hint 2: A dictionary can be used to store pre-calculated values,
    // this may allow a solution with O(N) complexity.
    var indexByValue = new Dictionary<int, int>();
    for (var i = 0; i < list.Count; i++) {
        var value = list[i];
        // ensure that the values used as keys are unique
        // this is OK because we only have to return any tuple matching the sum,
        // therefore we can ignore any duplicate values
        if (!indexByValue.ContainsKey(value)) {
            indexByValue.Add(value, i);
        }
    }
    
    for (var j = 0; j < list.Count; j++) {
        var remainder = sum - list[j];
        if (indexByValue.ContainsKey(remainder)) {
            return new Tuple<int, int> (j, indexByValue[remainder]);
        }
    }
    
    return null;
}