Dictionary.ContainsKey() не работает должным образом
В настоящее время я пытаюсь решить первую проблему с Leetcode (Две суммы):
Учитывая массив целых чисел nums и целочисленную цель, верните индексы из двух чисел так, чтобы они в сумме соответствовали целевому значению.
Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
Пример 1:
Ввод: числа = [2,7,11,15], цель = 9
Выход: [0,1]
Объяснение: Поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].
Пример 2:
Ввод: числа = [3,2,4], цель = 6
Выход: [1,2]
Пример 3:
Ввод: nums = [3,3], цель = 6
Выход: [0,1]
Вот мой код:
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> hash = new Dictionary<int, int>();
int n = nums.Count();
for (int i=0; i < n; i++) {
int complement = target - nums[i];
if (hash.ContainsKey(complement)) {
int[] solution = new int[]{(int)i, (int)hash[complement]};
return solution;
}
else {
hash.Add(nums[i], i);
}
}
return new int[]{};
}
Этот код работает нормально, пока я не получу список, содержащий один и тот же элемент несколько раз.
Например:
Входные данные: nums = [2,7,11,15], цель = 9.
Возвращает: [1,0]
Входные данные: числа = [1,1,1,1,1,4,1,1,1,1,1,7,1,1,1,1,1] цель = 11
Возвращает: «Необработанное исключение. System.ArgumentException: элемент с таким же ключом уже добавлен. Ключ: 1»
Итак, программа пытается добавить еще одну клавишу «1» в мой словарь. Я думаю, это потому, что даже если значение одинаковое, объект другой, но я не могу найти, как это решить.
Любая помощь ? Спасибо!
Я просто хочу отметить, что этот алгоритм работает отлично. См. этот код на Python (работает):
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hash:
return [i, hash[complement]]
else:
hash[nums[i]] = i
return []
Вы проверяете наличие дополнения в словаре, но затем добавляете nums[i] при его отсутствии. дополнение и nums[i] — это не одно и то же.
Вы не можете использовать словарь для решения этой проблемы. Для ввода примера [3,3] потребуется дважды ввести число 3 в ключ словаря, и в словаре может быть только одно число с одним и тем же ключом. Возможно, вам следует использовать индекс ключа вместо числа.
Ответы 1
Обратите внимание, что Add выдает исключение при попытке добавить тот же ключ; вместо этого вы можете использовать TryAdd
public int[] TwoSum(int[] nums, int target) {
...
else {
// Add a new key if and only if it doesn't exist
hash.TryAdd(nums[i], i);
}
...
}
Ваш код упрощен (.Length вместо Count(), TryGetValue вместо Contains и т. д.):
public class Solution {
public int[] TwoSum(int[] nums, int target) {
var hash = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; ++i)
if (hash.TryGetValue(target - nums[i], out int index))
return new int[]{index, i};
else
hash.TryAdd(nums[i], i);
return Array.Empty<int>();
}
}
Пожалуйста, поиграйте сами
Обновлено: обратите внимание, что вы проверяете разные ключи, например. для nums = {1, 1, ...} и target = 11 у вас есть второй элемент
hashсодержит один ключ1complement = 11 - 1 = 10- вы проверяете
hash.ContainsKey(complement)получаетеfalse(hashне содержит10) - вы пытаетесь добавить
1(обратите внимание,1не10) и получаете исключение
Спасибо, ваше предложение работает. Я просто не понимаю, почему программа вводит «еще», хотя она должна вводить его только тогда, когда ключ еще не присутствует в «хеше» (если).
@Simon Naulet: вы работаете с разными ключами: вы проверяете complement (скажем, 10, которого нет в hash), а затем пытаетесь добавить текущий item (скажем, 1, который находится в hash)
Сначала проверьте словарь и убедитесь, что он уже содержит значение, которое вы пытаетесь вставить. Хэш-набор не допускает дублирования записей.