Каждому по указателю

В этом уроке ты

Научишься решать задачи с помощью метода двух указателей «каждому по указателю».
Потренируешься на задаче с реального собеседования в BigTech.

Задача с собеседования

Представь, что ты снова на собеседовании. Для разминки интервьюер даёт тебе простую задачу:

Условие

Даны два монотонно возрастающих массива nums1 и nums2. Нужно вернуть массив nums3, который тоже будет монотонно возрастающим, и при этом содержать все общие элементы nums1 и nums2.

Монотонно возрастающий массив — это такой массив, в котором каждый следующий элемент больше или равен предыдущему (например, 1,2,2,2,3,4).

Пример

Ввод: nums1 = [-3,2,2,5,8,19,31], nums2 = [1,2,2,2,6,19,52]
Вывод: [2,2,19]

В чем сложность задачи?

Главная трудность — догадаться, что здесь стоит применить метод «двух указателей», и понять, как именно они должны двигаться. Если ты сможешь это осознать, решение будет найти довольно легко.

Оптимальное решение

Ставим два указателя — по одному на начало каждого массива. Затем:

Если элемент в nums1 меньше, чем в nums2, двигаем указатель p1.
Если элемент в nums1 больше, чем в nums2, двигаем указатель p2.
Если элементы равны, добавляем его в результат и двигаем оба указателя.

using System;
using System.Collections.Generic;

public class Solution
{
    public static List<int> Intersect(int[] nums1, int[] nums2)
    {
        int p1 = 0;
        int p2 = 0;
        List<int> res = new List<int>();

        // т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
        // равенство и если равны, двигаем оба указателя и прибавляем ответ
        // иначе двигаем указатель, который указывает на меньшее значение
        while (p1 < nums1.Length && p2 < nums2.Length)
        {
            if (nums1[p1] > nums2[p2])
            {
                p2++;
            }
            else if (nums1[p1] < nums2[p2])
            {
                p1++;
            }
            else
            {
                res.Add(nums1[p1]);
                p1++;
                p2++;
            }
        }

        return res;
    }
}

#include <vector>

using namespace std;

vector<int> intersect(const vector<int>& nums1, const vector<int>& nums2) {
    int p1 = 0;
    int p2 = 0;
    vector<int> res;
    
    // т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
    // равенство и если равны, двигаем оба указателя и прибавляем ответ
    // иначе двигаем указатель, который указывает на меньшее значение
    while (p1 < nums1.size() && p2 < nums2.size()) {
        if (nums1[p1] > nums2[p2]) {
            p2++;
        } else if (nums1[p1] < nums2[p2]) {
            p1++;
        } else {
            res.push_back(nums1[p1]);
            p1++;
            p2++;
        }
    }
    return res;
}

package main

func intersect(nums1 []int, nums2 []int) []int {
    p1 := 0
    p2 := 0
    var res []int
    
    // т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
    // равенство и если равны, двигаем оба указателя и прибавляем ответ
    // иначе двигаем указатель, который указывает на меньшее значение
    for p1 < len(nums1) && p2 < len(nums2) {
        if nums1[p1] > nums2[p2] {
            p2++
        } else if nums1[p1] < nums2[p2] {
            p1++
        } else {
            res = append(res, nums1[p1])
            p1++
            p2++
        }
    }
    
    return res
}

import java.util.*;

public class Solution {
    public List<Integer> intersect(List<Integer> nums1, List<Integer> nums2) {
        int p1 = 0;
        int p2 = 0;
        List<Integer> res = new ArrayList<>();
        
        // т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
        // равенство и если равны, двигаем оба указателя и прибавляем ответ
        // иначе двигаем указатель, который указывает на меньшее значение
        while (p1 < nums1.size() && p2 < nums2.size()) {
            if (nums1.get(p1) > nums2.get(p2)) {
                p2++;
            } else if (nums1.get(p1) < nums2.get(p2)) {
                p1++;
            } else {
                res.add(nums1.get(p1));
                p1++;
                p2++;
            }
        }
        
        return res;
    }
}

from typing import *

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
    p1 = 0
    p2 = 0
    res = []
    # т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
    # равенство и если равны, двигаем оба указателя и прибавляем ответ
    # иначе двигаем указатель, который указывает на меньшее значение
    while p1 < len(nums1) and p2 < len(nums2):
        if nums1[p1] > nums2[p2]:
            p2 += 1
        elif nums1[p1] < nums2[p2]:
            p1 += 1
        else:
            res.append(nums1[p1])
            p1 += 1
            p2 += 1
    return res

export function intersect(nums1, nums2) {
    let p1 = 0;
    let p2 = 0;
    const res = [];

    // т.к. мы можем иметь дубликаты, то на каждой итерации сравниваем на
    // равенство и если равны, двигаем оба указателя и прибавляем ответ
    // иначе двигаем указатель, который указывает на меньшее значение
    while (p1 < nums1.length && p2 < nums2.length) {
        if (nums1[p1] > nums2[p2]) {
            p2 += 1;
        } else if (nums1[p1] < nums2[p2]) {
            p1 += 1;
        } else {
            res.push(nums1[p1]);
            p1 += 1;
            p2 += 1;
        }
    }
    return res;
}

Время: O(n+m), где n - размер массива nums1, m - размер массива nums2
Память: O(min(n,m)), где n - размер массива nums1, m - размер массива nums2

Паттерн “каждому по указателю”

Принцип паттерна «каждому по указателю» таков: мы ставим указатели на начало нескольких массивов, а на каждом шаге сдвигаем один (или несколько) из них по определённому условию.

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

Что дальше

Переходи к практическим задачам, чтобы закрепить новые знания. Так ты сможешь быстро и уверенно решать подобные вопросы на собеседовании, даже если задача окажется сложной!