Как найти значение в C # Hashtable на основе текущего значения и получить ключ, а не TRUE или FALSE - PullRequest
Новая
       15

Как найти значение в C # Hashtable на основе текущего значения и получить ключ, а не TRUE или FALSE

0 голосов
/ 06 ноября 2019

Я пытался решить вопрос, который говорит: Проверьте, равняется ли СУММ любые два значения элемента из данного int [] данному значению суммы, верните истину, и ничего не найдено после проверки всех элементов, верните ложь.

Я решил это с помощью nested 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, он может добавить первый элемент вместе с собой и вернуть значение ИСТИНА, но, очевидно,Я не хочу, чтобы это произошло.

Итак, пожалуйста, как мне найти значение в Hashtable и получить ключ. В настоящее время функция возвращает TRUE или FALSE, основываясь на существовании значений.

1 Ответ

1 голос
/ 06 ноября 2019

Я думаю, это то, что вы ищете? Предполагая, что 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;
}

Мы используем HashSet<int>, который фактически является HashSet / Dictionary, который содержит только ключи. Для каждого возможного числа мы найдем остаток. Мы проверяем, что remainder != num (что решает проблему, например, sum, являющееся 4, num, равное 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), добавит накладные расходы.

...