Program JavaScript helah dua penunjuk

Teknologi penunjuk berganda untuk program JavaScript ialah kaedah algoritma yang biasa digunakan untuk menyelesaikan pelbagai masalah yang memerlukan kerumitan masa linear. Teknik ini digunakan secara meluas dalam penyelesaian masalah yang mencari, mengisih atau memanipulasi tatasusunan, rentetan atau senarai terpaut. Kaedah ini berfungsi dengan mengekalkan dua penunjuk, satu bermula dari permulaan struktur data dan satu lagi bermula dari penghujung, dan kemudian mengulanginya dalam arah yang bertentangan sehingga penyelesaian ditemui.

Dalam tutorial ini, kami akan meneroka konsep teknik penunjuk berganda dan cara melaksanakannya menggunakan bahasa pengaturcaraan JavaScript. Jadi mari kita mulakan dengan pernyataan masalah dahulu dan kemudian teruskan ke hadapan dengan tutorial yang menyeronokkan ini!

Pernyataan Masalah

Memandangkan tatasusunan A yang diisih dalam tertib menaik, mengandungi N integer, semak sama ada terdapat sebarang pasangan elemen (A[i], A[j]) supaya jumlahnya sama dengan X.

Sekarang marilah kita memahami kerja program di atas melalui beberapa contoh.

Input: const array = [1, 3, 5, 7, 9];
   const X = 12;
Output: Pair found at indices 1 and 4

Penjelasan − Dalam kes ini, pasangan elemen (3, 9) dalam tatasusunan input ditambah untuk memberikan jumlah sasaran 12, dan atur cara mengenal pasti pasangan elemen dengan indeks 1 dan 4 dengan betul.

Input: const array = [1, 3, 5, 7, 9];
   const X = 9;
Output: Pair not found

Penjelasan − Dalam kes ini, jika jumlah sasaran ialah 9, maka tiada pasangan sedemikian wujud dan fungsi harus mengembalikan "pair not found".

Algoritma

Algoritma menggunakan helah penunjuk berganda untuk mencari sama ada terdapat sepasang elemen dalam tatasusunan yang diisih yang jumlahnya sama dengan nilai sasaran yang diberikan -

• Mulakan dua penunjuk, kiri = 0, kanan = panjang tatasusunan - 1.

• Apabila bahagian kiri lebih kecil daripada bahagian kanan, lakukan operasi berikut

  • Kira jumlah elemen pada indeks kiri dan kanan.

  • Jika jumlahnya sama dengan nilai sasaran, kembalikan indeks kiri dan indeks kanan.

  • Jika jumlahnya kurang daripada nilai sasaran, naikkan bahagian kiri.

  • Jika jumlahnya lebih besar daripada nilai sasaran, kurangkan bahagian kanan.

• Jika tiada pasangan sedemikian wujud, kembalikan batal.

Algoritma di atas menggunakan teknik penunjuk berganda untuk mencari sepasang elemen dalam tatasusunan yang disusun supaya jumlahnya sama dengan nilai sasaran yang diberikan. Penunjuk bermula pada kedua-dua hujung tatasusunan dan bergerak ke arah satu sama lain berdasarkan cara jumlah elemen pada penuding dibandingkan dengan nilai sasaran. Jika jumlahnya kurang daripada nilai sasaran, gerakkan penunjuk kiri ke kanan untuk menambah jumlah. Jika jumlah lebih besar daripada nilai sasaran, gerakkan penunjuk kanan ke kiri untuk mengurangkan jumlah. Jika jumlahnya sama dengan nilai sasaran, program mengembalikan indeks pasangan elemen. Jika tiada pasangan elemen sedemikian wujud, atur cara mengembalikan Pair Not Found.

Sekarang marilah kita memahami algoritma ini melalui contoh, dalam contoh ini kita akan menggunakan JavaScript untuk melaksanakan pernyataan masalah yang dibincangkan sebelum ini.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Dalam atur cara ini, kami menggunakan Teknik Dua Penunjuk untuk mencari sama ada wujud sepasang elemen dalam tatasusunan diisih tertentu yang jumlahnya bersamaan dengan sasaran yang diberikan Dengan melelaran melalui tatasusunan dan menggerakkan penunjuk berdasarkan jumlah elemen pada penunjuk, program mencari pasangan elemen dengan cekap (jika wujud) dalam kerumitan masa O(N), dengan N ialah bilangan elemen dalam tatasusunan.

function findSumPair(array, X) {
   let left = 0;
   let right = array.length - 1;
   while (left < right) {
      const sum = array[left] + array[right];
      if (sum === X) {
         console.log(`Pair found at indices ${left} and ${right}`);
         return [left, right];
      } else if (sum < X) {
         left++;
      } else {
         right--;
      }
   }
   console.log('Pair not found');
   return null;
}
const array = [1, 3, 5, 7, 9];
const X = 12;
console.log(`Array: ${array}`);
console.log(`Target sum: ${X}`);
findSumPair(array, X);

Kesimpulan

Dalam tutorial ini, kami meneroka konsep teknik penunjuk berganda dan cara melaksanakannya menggunakan bahasa pengaturcaraan JavaScript untuk menyelesaikan masalah yang melibatkan pencarian atau membandingkan sepasang elemen dalam tatasusunan yang disusun. Kami juga mempelajari algoritma untuk mencari sepasang elemen supaya jumlahnya sama dengan sasaran tertentu menggunakan teknik dua mata. Dengan menggunakan teknik ini, kami boleh meningkatkan kecekapan program kami dengan ketara dari segi kerumitan masa. Khususnya, teknologi penuding dua boleh menyelesaikan jenis masalah ini dalam kerumitan masa O(N), yang jauh lebih pantas daripada kaedah kekerasan O(N^2). Oleh itu, adalah sangat penting untuk mempelajari dan menggunakan teknik ini untuk menyelesaikan masalah yang sama dengan cekap.

Atas ialah kandungan terperinci Program JavaScript helah dua penunjuk. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!