Эрэмбэлэгдсэн array-н хоёр захаас l, r заагчийг ойртуулж, нийлбэр нь x болох хосыг олдог арга.

Pre-IntermediateХугацаа: O(n)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = [1, 2, 4, 7, 11] дотроос нийлбэр нь 9 болох хоёр тоо хайя. l = 0, r = 4: 1 + 11 = 12 их тул r-ыг зүүн тийш. 1 + 7 = 8 бага тул l-ийг баруун тийш. 2 + 7 = 9. Олдлоо!

Хариу 2 7. Гуравхан нийлбэр бодлоо.

Энгийн аргаас санаа руу

Бүх хосыг шалгавал n(n - 1) / 2 хос, n = 10⁵ бол 5 тэрбум орчим. Удаан.

Array эрэмбэлэгдсэн гэдгийг ашиглая. Хамгийн бага a[l], хамгийн их a[r] хоёрыг нэмье. Нийлбэр их бол a[r] ямар ч тоотой нийлээд хэт их, учир нь a[l] хамгийн бага нь байсан. Тиймээс a[r]-ыг хаяж r--. Нийлбэр бага бол ижил шалтгаанаар a[l]-ийг хаяж l++. Алхам бүрт нэг тоо хасагдана.

Нэр томьёо ба тэмдэглэгээ

l, r
Зүүн ба баруун заагч. Хариунд орж болох тоонууд үргэлж a[l]-ээс a[r] хүртэлх хэсэгт байна.
s
Одоогийн нийлбэр: a[l] + a[r].
x
Хайж буй нийлбэр.
эрэмбэлэгдсэн array
Энэ аргын гол нөхцөл. Эрэмбэгүй бол эхлээд sort хийнэ.
a
1
0l
3
1
4
2
6
3
8
4
11
5
14
6r
x = 10l = 0r = 6

Эрэмбэлэгдсэн array-гээс нийлбэр нь 10 болох хоёр тоо хайна. l зүүн захаас, r баруун захаас эхэлнэ.

Алхам 1 / 13
Хурд
  • a[l] ба a[r]
  • Олдсон хос
  • Хасагдсан
Слайд 1 / 7

Two Pointers

Эрэмбэлэгдсэн array-гээс нийлбэр нь 10 болох хоёр тоо хайна. l зүүн захаас, r баруун захаас бие бие рүүгээ алхана.

two-pointers.cpp
#include <bits/stdc++.h>
using namespace std;
int n, x, a[100005];
int main() {
cin >> n >> x;
for (int i = 0; i < n; i++) cin >> a[i];
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == x) {
cout << a[l] << ' ' << a[r] << '\n';
return 0;
}
if (s < x) {
l++;
} else {
r--;
}
}
cout << -1 << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Эрэмбэлэгдсэн array-гээс нийлбэр нь x болох хоёр тоо олох. Бүх хосыг шалгавал n × n алхам, энэ арга n алхам хийнэ.

Яаж ажилладаг вэ?

1. l = 0 (хамгийн бага тоо), r = n − 1 (хамгийн их тоо). 2. s = a[l] + a[r]. 3. s = x бол хос олдлоо. 4. s < x бол нийлбэр бага: l баруун тийш алхана. 5. s > x бол нийлбэр их: r зүүн тийш алхана. 6. l, r уулзвал хос алга, хариу -1. Оролт: n x, дараа нь өсөх дарааллаар n тоо.

Яагаад зөв, хэр хурдан бэ?

Хариу хос нь a[i] + a[j] = x байг. l нь i-д хүрсэн үед r нь j-ээс багагүй бол нийлбэр x-ээс бага биш. Тиймээс l хөдлөхгүй, зөвхөн r багасна. Үүнтэй адилаар r нь j-д хүрсэн үед l л хөдөлнө. Тэгэхээр заагчид хариу хосыг алгасахгүй.

Алхам бүрт r - l нэгээр багасна: n-ээс цөөн алхам, хугацаа O(n). Эрэмбэлэх шаардлагатай бол O(n log n). n = 100 000 бол 100 000 хүрэхгүй алхам.

Түгээмэл алдаа

  • Эрэмбэлэгдээгүй array дээр хэрэглэх. Эхлээд sort(a, a + n).
  • while (l <= r) гэж бичвэл нэг тоог өөртэй нь нэмж, 2 · a[l] = x үед буруу хос гаргана.
  • Тоо 10⁹ хүртэл бол a[l] + a[r] int-ээс хэтэрч болно. long long ашигла.
  • Чиглэлийг андуурах: нийлбэр бага үед r-ыг багасгавал нийлбэр улам багасна.

Хязгаарын тохиолдол

  • n = 1: l < r худал, шууд -1.
  • Хос байхгүй: l, r уулзаад -1.
  • Ижил тоонууд [5, 5], x = 10: хоёр өөр index тул зөв хос.
  • Хэд хэдэн хос байвал: аль нэгийг нь олно.

Өөрийгөө шалга

  1. Анхдагч жишээ 1 3 4 6 8 11 14, x = 10 дээр хэдэн нийлбэр бодох вэ?

    Хариу харах

    6: 15, 12, 9, 11, 9, 10. Хариу 4 6.

  2. Нийлбэр бага үед l-ийг нэмэх нь яагаад зөв бэ?

    Хариу харах

    a[l] нь хамгийн их a[r]-тай нийлсэн ч x-д хүрэхгүй. Бусад тоотой нийлбэл бүр бага. Тиймээс a[l] хэзээ ч хариунд орохгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [2, 3, 5, 8, 13], x = 16 үед l, r, s-ийн утгыг алхам алхмаар бич.

    Hint харах

    Эхлээд l = 0, r = 4.

    Хариу ба тайлбар

    s = 2 + 13 = 15 < 16 тул l = 1. s = 3 + 13 = 16. Хариу 3 13.

  2. 2.Нийлбэр нь яг x болох хос хэд байгааг тоол (тоонууд бүгд ялгаатай).

    Hint харах

    Хос олдсоны дараа аль заагчийг хөдөлгөх вэ?

    Хариу ба тайлбар

    Олдвол cnt++ хийгээд l++, r-- хоёуланг нь хөдөлгөнө. Тоонууд ялгаатай тул тэр хоёр тоо өөр хосонд орохгүй.

  3. 3.Эрэмбэлэгдсэн array-д нийлбэр нь x болох гурван тоо ол (3SUM), n ≤ 3000.

    Hint харах

    Нэг тоог тогтоогоод, үлдсэн хэсэгт Two Pointers ажиллуул.

    Хариу ба тайлбар

    i бүрт l = i + 1, r = n - 1 гэж эхлүүлээд нийлбэр нь x - a[i] болох хосыг Two Pointers ашиглан хайна. Нийт O(n²), n = 3000 бол 9 сая орчим алхам.

Жишээ

Оролт

7 10
1 3 4 6 8 11 14

Гаралт

4 6

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.