C# | LeetCode

Задача: №18. 4Sum #medium Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что: 0 <= a, b, c, d < n a, b, c и d различны. nums[a] + nums[b] + nums[c] + nums[d] == цель Вы можете вернуть ответ в любом порядке.

Решение:

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        var rs = new List<IList<int>>();
        Array.Sort(nums);
        Helper(rs, nums, target, 4, 0, new List<int>());
        return rs;
    }

    private void Helper(List<IList<int>> rs, int[] nums, long target, int k, int index, List<int> subList) {
        if (k == 2) {
            int l = index;
            int r = nums.Length - 1;
            while (l < r) {
                long sum = nums[l] + nums[r];
                if (sum == target) {
                    subList.Add(nums[l]);
                    subList.Add(nums[r]);
                    rs.Add(new List<int>(subList));
                    subList.RemoveAt(subList.Count - 1);
                    subList.RemoveAt(subList.Count - 1);
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r - 1] == nums[r]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        } else {
            for (int i = index; i < nums.Length - k + 1; i++) {
                if (i != index && nums[i] == nums[i - 1]) {
                    continue;
                }
                subList.Add(nums[i]);
                Helper(rs, nums, target - nums[i], k - 1, i + 1, subList);
                subList.RemoveAt(subList.Count - 1);
            }
        }
    }
}

Пояснение: Метод FourSum: Этот метод инициализирует основной процесс поиска, создавая список rs для хранения результатов. Массив nums сортируется для упрощения дальнейшей логики. Затем вызывается вспомогательный метод Helper с параметрами: результатами, отсортированным массивом, целевым значением, количеством элементов для поиска (в данном случае 4), начальным индексом и пустым списком для временного хранения текущего поднабора. Метод Helper: Этот метод рекурсивно находит наборы чисел, которые соответствуют заданному количеству k и суммируются до указанного целевого значения target. База рекурсии (k == 2): Когда требуется найти пары чисел, функция использует двухуказательный подход. l начинает с начального индекса, r — с конца массива. В цикле проверяется сумма чисел на этих позициях: Если сумма равна target, текущая пара добавляется в временный список subList, и результат добавляется в основной список rs. После добавления результаты очищаются для следующего возможного набора. Если сумма меньше target, увеличивается индекс l, чтобы попробовать большее число. Если сумма больше target, уменьшается индекс r, чтобы попробовать меньшее число. Рекурсивный вызов (k > 2): При большем количестве элементов для поиска (например, 4) метод перебирает элементы массива начиная с указанного индекса. Для каждого элемента: Если текущий элемент такой же, как предыдущий, пропускается, чтобы избежать дублирования. Текущий элемент добавляется в subList, и вызывается рекурсивно с уменьшением k на 1 и обновлением целевого значения (target - nums[i]). После возвращения из рекурсии элемент удаляется из subList для возможности обработки следующих комбинаций. Временная и пространственная сложность: Временная сложность: О(n^3), так как в самом худшем случае каждая из рекурсий может быть вызвана до трех уровней вложенности, где n — длина массива nums. Пространственная сложность: O(n), включая список для хранения подмножеств и рекурсивный стек.

Задача: №17. Letter Combinations of a Phone Number #medium Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

public class Solution 
{
    Dictionary<char, char[]> keypad = new Dictionary<char, char[]> {{'2', new char[]{'a', 'b', 'c'}}, 
    {'3', new char[]{'d', 'e', 'f'}}, {'4', new char[] {'g', 'h', 'i'}}, 
    {'5', new char[] {'j', 'k', 'l'}}, {'6', new char[] {'m', 'n', 'o'}}, 
    {'7', new char[] {'p', 'q', 'r', 's'}}, {'8', new char[] {'t', 'u', 'v'}}, 
    {'9', new char[] {'w', 'x', 'y', 'z'}}};

    public void AddCombination(string curr, string digits, int index, IList<string> list)
    {
        if(index >= digits.Length) list.Add(curr);
        else
        {
            char[] map = keypad[digits[index]];

            for(int i = 0; i < map.Length; i++)
            {
                string newCurr = curr + map[i];

                AddCombination(newCurr, digits, index + 1, list);
            }
        }
    }

    public IList<string> LetterCombinations(string digits) 
    {
        IList<string> combinations = new List<string>();

        if(digits.Length > 0) AddCombination("", digits, 0, combinations);

        return combinations;
    }
}

Пояснение: Определение карты клавиатуры: Словарь keypad содержит маппинг между цифрами и буквами, которые соответствуют этим цифрам на традиционной телефонной клавиатуре. Например, цифра '2' соответствует буквам 'a', 'b', 'c'. Метод AddCombination: Этот метод рекурсивно генерирует все возможные комбинации букв. Принимает текущую комбинацию curr, строку цифр digits, текущий индекс index и список list, в который добавляются найденные комбинации. Если индекс выходит за границы строки digits, это означает, что все цифры обработаны, и текущая комбинация добавляется в список list. Если не все цифры обработаны, метод получает массив букв, соответствующих текущей цифре, из словаря keypad. Для каждой буквы в массиве создаётся новая комбинация, и вызывается рекурсивный вызов метода для следующей цифры. Метод LetterCombinations: Этот метод инициализирует процесс генерации комбинаций, создавая список combinations для хранения результатов. Если входная строка digits не пуста, вызывается метод AddCombination с начальными параметрами: пустой строкой для текущей комбинации, строкой цифр, начальным индексом 0 и списком результатов. Возвращает список всех возможных комбинаций букв. Временная и пространственная сложность: Временная сложность: O(3^n), где n — количество цифр в строке digits. Это связано с тем, что для каждой цифры на клавиатуре есть набор соответствующих букв, и для каждой цифры мы можем иметь 3 или 4 комбинации, в зависимости от цифры. Пространственная сложность: O(3^n), так как в худшем случае мы сохраняем все возможные комбинации в списке.

Задача: №16. 3Sum Closest #medium Условие:

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

Решение:

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        if(nums.Length < 3)
            return 0;

        Array.Sort(nums);
        int start = 0;
        int left = 1;
        int right = nums.Length - 1;
        int direction = nums[start] + nums[left] + nums[right] > 0 ? 1 : 0;
        int minDistance = int.MaxValue;
        int sum = int.MinValue;

        while (start < nums.Length - 2)
        {
            while (left < right)
            {
                int currSum = nums[start] + nums[left] + nums[right];
                if ( currSum == target )
                    return target;
                
                if (currSum < target)
                    left++;
                else 
                    right--;

                if (Math.Abs(currSum - target) < minDistance)
                {
                    sum = currSum;
                    minDistance = Math.Abs(currSum - target);
                }
            }
            start ++;
            left = start + 1;
            right = nums.Length - 1;
        }
        return sum;
    }
}

Пояснение : Проверка длины массива: Сначала проверяется, содержит ли массив nums хотя бы три элемента. Если нет, метод возвращает 0, так как нет смысла искать сумму трёх элементов. Сортировка массива: Массив nums сортируется. Это необходимо для упрощения поиска комбинаций с использованием двух указателей. Инициализация переменных: start инициализируется на первом элементе, left на втором, и right на последнем элементе массива. Переменные direction, minDistance, и sum инициализируются для отслеживания минимального расстояния до целевой суммы и самого близкого найденного значения суммы. Внешний цикл: Внешний цикл перебирает элементы массива начиная с первого. Для каждого элемента start он рассматривает комбинации элементов с использованием двух других указателей (left и right). Внутренний цикл: Внутренний цикл выполняется до тех пор, пока указатели left и right не пересекутся. Рассчитывается сумма элементов, на которые указывают указатели start, left, и right. Если сумма совпадает с целевой суммой, возвращается целевая сумма, так как это идеальный случай. Обновление указателей и значений: Если сумма меньше целевой, left сдвигается вправо (увеличивается), чтобы увеличить сумму. Если сумма больше целевой, right сдвигается влево (уменьшается), чтобы уменьшить сумму. При каждом изменении указателей обновляется минимальное расстояние между текущей суммой и целевой суммой, если новое расстояние меньше текущего. Возвращение результата: После завершения всех итераций возвращается значение sum, которое является суммой трех элементов, ближайшей к целевой сумме. Временная и пространственная сложность: Временная сложность: O(n^2), где n — количество элементов в массиве. Основная сложность обусловлена двойным перебором элементов массива (внешний цикл и внутренний цикл). Пространственная сложность: O(1), так как используется фиксированное количество переменных для хранения данных и индексов, не зависящих от размера входных данных.