c# Метод расширения словаря FirstOrDefault не возвращает ожидаемое значение

Question

Я пытаюсь решить проблему leetcode twoSum, где:

Учитывая массив целых чисел, возвращайте индексы двух чисел так, чтобы они складывались до определенной c цели. Вы можете предположить, что у каждого ввода будет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Итак, вот мой метод:

    static public int[] TwoSum(int[] nums, int target)
    {
        Dictionary<int, int> numberAndComplement = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int complement = target - (int)nums[i];
            if (numberAndComplement.ContainsValue(nums[i]))
            {
               int[] vs =  { numberAndComplement.FirstOrDefault(x => x.Value == complement).Key, i}; 
               return vs;
            }
            numberAndComplement.Add(i, complement);
        }
        return new int[] { 0, 0 };

При передаче [ 3,2,4], 6 Я ожидал, что в качестве ответа будут индексы [1,2], но вместо этого я получаю [0,2], что не имеет смысла, потому что это не ошибка на одну ошибку. Так как я использую FirstOrDefault, я должен получить 1 обратно, и это сводит меня с ума.

Answer 1

Это решение также будет проходить через:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var indices = new Dictionary<int, int>();

        for (int index = 0; index < nums.Length; index++) {
            if (indices.ContainsKey(target - nums[index])) {
                return new int[] { indices[target - nums[index]], index };

            }

            if (!indices.ContainsKey(nums[index])) {
                indices.Add(nums[index], index);
            }
        }

        return null;
    }
}

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Существует множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптотических c времени / пробела анализа сложности ^{1 , 2} там.

Если вы готовитесь к собеседованию :

• Мы хотели бы написать коды без ошибок и чистые на основе стандартов и соглашений (например, c ^{1 , 2} , c ++ ^{1 , 2} , java ^{1 , 2} , c# ^{1 , 2} , python ¹ , javascript ¹ , go ¹ , ржавчина ¹ ).

Answer 2

Код кажется неправильным -if (numberAndComplement.ContainsValue (nums [i])) - необходимо искать дополнение, поскольку число уже находится в i.

static public int[] TwoSum(int[] nums, int target)
{
    Dictionary<int, int> numberAndComplement = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - (int)nums[i];
        
        if (numberAndComplement.ContainsValue(complement))
        {
           int[] vs =  { numberAndComplement.FirstOrDefault(x => x.Value == complement).Key, i}; 
           return vs;
        }
        numberAndComplement.Add(i, nums[i]);
    }
    return new int[] { 0, 0 };
}

Answer 3

Зачем вам вообще numberAndComplement Словарь? Вычислите дополнение и используйте Array.IndexOf () , чтобы напрямую увидеть, присутствует ли искомое число в исходном массиве. Просто убедитесь, что возвращенный индекс не совпадает с текущим значением i в вашем l oop:

static public Tuple<int, int> TwoSum(int[] nums, int target)
{
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        int complementIndex = Array.IndexOf(nums, complement);
        if (complementIndex != -1 && complementIndex != i)
        {
            return new Tuple<int, int>(i, complementIndex);
        }
    }
    return null;
}