Երբ աշխատում ենք զանգվածների հետ, «սահող պատուհան» մեթոդը (sliding window) լայնորեն կիրառվող մեթոդ է, որը թույլ է տալիս արդյունավետ լուծել խնդիրներ՝ օգտագործելով երկու ցուցիչ (ձախ և աջ): Սահող պատուհանi hիմնական գաղափարն այն է, որ այդ երկու ցուցիչները տեղափոխենք ճիշտ ուղղություններով, այն ժամանակ, երբ դա անհրաժեշտ է։
Պատկերացրեք, որ ցանկանում ենք գտնել որոշ օպտիմալ ենթազանգված (subarray) զանգվածի մեջ. նախ որքան հնարավոր է աջ ցուցիչը տեղափոխում ենք առաջ, հետո սկսում ենք ձախ ցուցիչով «բերել» աջի հետևից, որ հասնենք ճիշտ միջակայքին։ Այնուհետև նորից աջ ցուցիչը տանում ենք առաջ, հետո ձախը տեղափոխում՝ փորձելով ստանալ լավագույն տարբերակը։ Այս գործընթացը կրկնվում է այնքան ժամանակ, մինչեւ գտնենք մեզ հարկավոր միջակայքը․ սա հենց «սահող պատուհան» մեթոդն է։
Առաջադրանք - Գտնել երկու թվեր, որոնց գումարը հավասար է k-ի
Տրված է աճման կարգով դասավորված n տարրից կազմված զանգված և k թիվը։ Պետք է գտնել այդ զանգվածից այն երկու թվերը, որոնց գումարը հավասար է k-ի։ Ուշադրություն դարձրեք, որ զանգվածի տարրերը դասավորված են աճման կարգով և դուք չեք կարող օգտագործել dictionary, map, hashmap և այլն։
Մուտք
Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ՝ n (1 ≤ n ≤ ) և k ()։ Հաջորդ տողում տրված են n ամբողջ թվեր, որոնք դասավորված են աճման կարգով ():
Ելք
Ծրագիրը պետք է տպի զանգվածի այն երկու ամբողջ թվերը, որոնց գումարը հավասար է k-ի։ Առաջինը պետք է լինի հնարավոր ամենափոքր թիվը։ Եթե նման զույգ գտնել հնարավոր չէ, ծրագիրը պետք է տպի Impossible։
Օրինակներ
Мուտք
Ելք
5 11
-2 3 4 8 9
3 8
5 1000
-2 3 4 8 9
Impossible
Ուղեցույց
Քանի որ զանգվածը աճման կարգով է դասավորված, կարող ենք սկսել ձախ և աջ ցուցիչներից (համապատասխանաբար զանգվածի սկզբում և վերջում) և կախված այդ երկուսի գումարից՝ փոխել ցուցիչների դիրքը։
Եթե այդ երկու թվերի գումարը մեծ է k-ից, նվազեցնում ենք աջ ցուցիչը։ Եթե գումարը փոքր է k-ից, մեծացնում ենք ձախ ցուցիչը։ Եվ եթե գումարը հավասար է k-ի, անմիջապես տպում ենք այդ թվերը և ավարտում ծրագիրը։
n, k = ... # Մուտքագրում ենք n և k
a = ... # Մուտքագրում ենք զանգվածը (այն աճման կարգով է դասավորված)
l, r = 0, len(a) - 1 # Սահող պատուհանի ձախ և աջ ցուցիչների սկզբնական դիրքերը
while l < r: # Քանի դեռ l և r տարբեր են
if a[l] + a[r] > k: # Եթե գումարը մեծ է k-ից => փոքրացնենք այն r-ն նվազեցնելով
r -= 1
elif a[l] + a[r] < k: # Եթե գումարը փոքր է k-ից => մեծացնենք այն l-ն մեծացնելով
l += 1
else: # a[l] + a[r] == k => տպում ենք և դադարեցնում
print(a[l], a[r])
break
else: # while...else = ոչ մի break -> ոչինչ չգտանք
print('Impossible')
«Երկու ցուցիչների» գաղափարը շատ տարբեր տեղեր կարող է օգտագործվել՝ բազմաթիվ խնդիրներում։ Գլխավոր սկզբունքն այն է, որ ընտրում ենք ձախ և աջ ցուցիչների նախնական դիրքերը (որոնք կարող են շատ տարբեր լինել տարբեր խնդիրների դեպքում) և սահմանում ենք, թե ինչպե՛ս պետք է փոխվեն այդ ցուցիչները։
Մեր օրինակու՛մ ձախ ցուցիչը վերցրինք զանգվածի սկզբում, իսկ աջը՝ վերջում։ Սակայն այլ խնդիրներում հնարավոր է, որ երկու ցուցիչներն էլ դրվեն զանգվածի սկզբում, կամ մեկ այլ տարբերակով. ամեն ինչ կախված է խնդրի պահանջներից ու ձեր ընտրած կիրառման ձևից։