Mötas på mitten
Halvera exponenten genom att dela sökningen
Mötas på mitten är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
När brute force går för långsamt
Vissa problem har N omkring 40, där det är hopplöst att prova alla delmängder av typen 2^N. Meet-in-the-middle räddar dessa medelstora fall. 🤝
Grundidén
Dela indata i två halvor. Lös varje halva med brute force och kombinera sedan de två delresultaten på ett smart sätt.
Halvera exponenten
Två halvor med storleken N/2 kostar vardera 2^(N/2) i stället för totalt 2^N. Den här kvadratrotsminskningen förvandlar 2^40 till hanterbara 2^20.
Ett klassiskt mål: subset sum
Fråga om någon delmängd summerar till ett målvärde T. Subset sum med N nära 40 är det klassiska meet-in-the-middle-problemet.
Enumerera den första halvan
Lista varje delmängdssumma i den vänstra halvan och lagra dem. Med N/2 element blir det bara 2^(N/2) summor.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Enumerera den andra halvan
Gör samma sak för den högra halvan och bygg dess fullständiga lista med delmängdssummor. Nu har Ni två hanterbara listor.
Kombinera med en uppslagning
För varje högersumma r behöver Ni en vänstersumma som är lika med T - r. En mängd eller sorterad lista gör kontrollen snabb.
need = T - r
found = need in left_setTvå sätt att matcha
För exakta målvärden används en hash set. För räkning eller närmaste summor sorterar Ni ena halvan och gör en binärsökning i den.
Tidskostnaden
Det totala arbetet är ungefär 2^(N/2) gånger en logaritmisk faktor för sökningen eller sorteringen. Den komplexiteten är det som gör N nära 40 hanterbart.
Minnet är avvägningen
Ni lagrar en hel halva, så minnesåtgången växer till 2^(N/2). Behåll bara det Ni måste för att hålla Er inom gränsen.
Fler användningsområden
Utöver subset sum kan Ni använda metoden för maximal delmängd under en gräns, räkning av par och diskret-logaritmliknande problem. Den trivs med en ren uppdelning.
Snabbkontroll
Ni använder meet-in-the-middle på ett delmängdsproblem med N element. Vad är den ungefärliga tidskostnaden?
Sammanfattning
Dela upp i två halvor, använd brute force på varje halva och matcha sedan vänster- och högersummorna. Ni bytte lite extra minne mot en enorm hastighetsökning. 🚀
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Mötas på mitten” gratis?
Ja – hela texten till ”Mötas på mitten” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Mötas på mitten”?
Halvera exponenten genom att dela sökningen Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Mötas på mitten”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Vinnande och förlorande tillstånd i spel
- Nim och Grundy-tal
- Mötas på mitten
- Felsök snabbt: stresstester och triage