Эки көрсөткүч ыкмасы
Эки көрсөткүч ыкмасы: берилген суммадагы түгөйлөр жана O(n) убакыттагы жылма терезе.
Ыкманын идеясы: эки индекс массив боюнча алдыга гана (же бири-бирине карай) жүрөт жана эч качан артка кайтпайт. Ар бир көрсөткүч n ден көп эмес жолу жылат — жыйынтыгында бардык түгөйлөрдү кыдырган O(n²) ордуна O(n).
Биринчи классика: ИРЕТТЕЛГЕН массивден суммасы X болгон түгөйдү табуу. Көрсөткүчтөрдү четтерине коёбуз: сумма аз болсо — солдогусун оңго жылдырабыз (сумма өсөт), көп болсо — оңдогусун солго.
Суммасы X болгон түгөй. Киргизиңиз: 5 12, андан кийин иреттелген массив 1 3 5 7 9
Бул эмнеге туура: эгер a[l] + a[r] < X болсо, анда a[l] r ден солдогу КААЛАГАН элемент менен түгөйлөшкөндө андан да аз берет — демек, a[l] санын тайманбастан чыгарып салса болот. Оң жагы үчүн симметриялуу. Бир да мүмкүн болгон түгөй жоголбойт.
Экинчи классика — жылма терезе: эки көрсөткүч тең бир багытта жүрөт. Суммасы S тен ашпаган эң узун кесиндини табалы: оң чет терезени кеңейтет, сумма лимиттен ашканда сол чет кысылат.
Суммасы S тен ашпаган эң узун кесинди. Киргизиңиз: 6 8, андан кийин 2 4 1 3 5 2
Көңүл буруңуз: ички while алгоритмди квадраттык кылбайт — сол көрсөткүч программанын бүт иши боюнча жалпысынан n ден көп эмес жолу жылат.
Тил курсунда жазган палиндром текшерүүңүз — бул да бири-бирине карай жүргөн эки көрсөткүч. Тиркелген «Палиндромду текшерүү» маселесин эми ыкманын жеке учуру катары аңдап туруп чечиңиз да, сабакты өттүм деп белгилеңиз.