c# - 如何根据当前值在 C# Hashtable 中搜索值并获取键而不是 TRUE 或 FALSE

Question

我试图解决一个问题，即检查给定 int[] 中的任何两个元素值的 SUM 是否等于给定的总和值，返回 true 并且在检查所有元素后未找到任何内容，返回 false。

我使用嵌套的 for..loop 轻松解决了这个问题，如下所示：

public bool CheckValue (int[] given, int sum) {
    if (given == null) {
        return false;
    } else if (given.Length == 0 || given.Length == 1) {
        return false;
    } else {
        for (int i = 0; i < given.Length - 1; i++) {
            for (int j = i + 1; j < given.Length; j++) {
                if ((given[i] + given[j]) == sum) {
                    return true;
                }
            }
        }

        return false;
    }
}

但我想在第二个循环中使用 Hashtable 来解决它，因为它会简化搜索过程并尝试以下代码：

private static bool CheckValueUsingHashTable (int[] given, int sum) {
    if (given == null) {
        return false;
    } else if (given.Length == 0 || given.Length == 1) {
        return false;
    } else {
        Hashtable hashs = new Hashtable ();

        for (int i = 0; i < given.Length; i++) {
            hashs.Add (i, given[i]);
        }

        for (int j = 0; j < given.Length; j++) {
            int valueToAdd = sum - given[j];
            if (hashs.ContainsValue (valueToAdd)) {
                return true;
            }
        }

        return false;
    }
}

我现在面临的问题是，如果给定的数组是 {1,2,3,4} 并且给定的总和是 2，它可以将第一个元素与自身相加并返回 TRUE，但显然，我不希望这种情况发生。

那么，请问如何从哈希表中搜索值并获取密钥。目前，该函数根据值的存在返回 TRUE 或 FALSE。

标签： c#hashtable

Answer 1

我想这就是你所追求的？假设given不能两次包含相同的数字。

public static bool CheckValue(int[] given, int sum)
{
    if (given == null)
    {
        return false;
    }
    if (given.Length == 0 || given.Length == 1)
    {
        return false;
    }

    var hashSet = new HashSet<int>(given);

    foreach (int num in given)
    {
        int remainder = sum - num;
        if (remainder != num && hashSet.Contains(remainder))
        {
            return true;
        }
    }

    return false;
}

我们使用 a HashSet<int>，它实际上是一个仅包含键的 HashSet/Dictionary。对于每个可能的数字，我们找到余数。我们检查它remainder != num（这解决了如sumbeing 4、numbeing 2 和我们发现2存在于的问题hashSet），然后查看余数是否在我们的HashSet 中。

您可以添加另一个优化，前提是given已排序：

foreach (int num in given)
{
    int remainder = sum - num;
    if (remainder != num && hashSet.Contains(remainder))
    {
        return true;
    }

    // Addition is commutative (1 + 2 == 2 + 1), so if we're past the half-way point,
    // we're not going to find anything
    if (num > sum/2)
    {
        return false;   
    }
}

---

但是，除非given非常大，否则这几乎肯定会比您问题中的幼稚解决方案慢。直接比较整数是非常快的，而且HashSet<T>虽然 O(n) 会增加开销。