Bagaimana untuk mencari subrentetan tidak berulang dalam JavaScript

Dalam pembangunan sebenar, kita selalunya perlu melakukan beberapa operasi dan pemprosesan pada rentetan, salah satunya ialah mencari subrentetan tidak berulang. Contohnya, dalam rentetan "abcabcbb", subrentetan tidak berulang terpanjang ialah "abc", dan dalam rentetan "bbbbbb", subrentetan tidak berulang terpanjang ialah "b". Masalah ini dikenali dalam algoritma sebagai masalah "subrentetan tidak berulang terpanjang" dan kami boleh menyelesaikannya menggunakan JavaScript.

1. Kaedah penghitungan ganas

Kaedah yang paling mudah ialah menggunakan kaedah penghitungan brute force, iaitu, melintasi rentetan dari awal untuk setiap aksara dan menambah aksara tidak berulang satu demi satu sehingga aksara berulang ditemui. Kemudian, rekod panjang subrentetan pada masa ini, tetapkan semula subrentetan dan teruskan melintasi rentetan ke bawah sehingga penghujung traversal.

Kodnya adalah seperti berikut:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  for(let i = 0; i < str.length; i++) {
    let map = new Map(); // 定义 Map 来保存子串中元素出现的次数
    let length = 0; // 定义子串长度为 0
    for(let j = i; j < str.length; j++) {
      if(map.has(str[j])) { // 如果子串中已经有这个元素了
        maxLength = Math.max(maxLength, length); // 更新最大长度
        break; // 说明这个子串已经不符合要求了，跳出内部循环
      } else {
        map.set(str[j], 1); // 在 Map 中记录该元素的出现次数
        length++; // 子串长度 +1
        maxLength = Math.max(maxLength, length); // 更新最大长度
      }
    }
  }
  return maxLength;
}

Kerumitan masa kaedah ini ialah O(n^3) Memandangkan bilangan gelung bersarang adalah sangat besar, apabila memproses rentetan yang lebih panjang kecekapan adalah sangat rendah.

2. Kaedah tetingkap gelongsor

Untuk meningkatkan kecekapan, kita boleh menggunakan kaedah tetingkap gelongsor. Idea tetingkap gelongsor adalah untuk mengekalkan tetingkap panjang k dan luncurkan tetingkap ini untuk memproses rentetan. Dalam masalah ini, panjang tetingkap gelongsor ialah panjang rentetan tidak berulang.

Secara khusus, apabila melintasi rentetan, kami mentakrifkan penunjuk permulaan dan penuding penamat, dan kedua-dua penunjuk ini akan membentuk tetingkap. Dalam setiap gelung, jika elemen yang ditunjuk oleh penuding akhir tidak wujud dalam tetingkap, kita boleh menambahkannya pada tetingkap, kemudian mengembangkan tetingkap dan mengemas kini panjang tetingkap. Jika elemen yang ditunjuk oleh penuding akhir sudah wujud dalam tetingkap, kita perlu mengalihkan penuding mula ke kanan dan mengecilkan tetingkap sehingga elemen yang ditunjuk oleh penuding akhir tidak lagi wujud dalam tetingkap. Dalam proses ini, kita perlu menggunakan jadual pemetaan untuk merekodkan bilangan kejadian setiap elemen dalam tetingkap.

Kodnya adalah seperti berikut:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  let map = new Map(); // 定义 Map 来保存元素出现的次数
  let left = 0; // 定义左指针为 0
  for(let right = 0; right < str.length; right++) {
    if(map.has(str[right])) { // 如果窗口内已经有该元素了
      left = Math.max(left, map.get(str[right]) + 1); // 更新左指针，向右移动
    }
    map.set(str[right], right); // 在 Map 中记录该元素的位置
    maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
  }
  return maxLength;
}

Kerumitan masa kaedah tetingkap gelongsor ialah O(n) Ia menggunakan HashMap untuk mencari dan menyimpan aksara dengan cepat cekap daripada kaedah penghitungan brute force .

3. Ringkasan

Untuk masalah subrentetan tidak berulang terpanjang dalam rentetan, kita boleh menggunakan dua kaedah untuk menyelesaikannya: kaedah penghitungan brute force dan kaedah tetingkap gelongsor. Kaedah penghitungan brute force mempunyai kerumitan masa yang tinggi, manakala kaedah tetingkap gelongsor adalah lebih cekap. Dalam perkembangan sebenar, kita boleh memilih kaedah yang sesuai untuk menyelesaikan masalah mengikut keperluan.

Atas ialah kandungan terperinci Bagaimana untuk mencari subrentetan tidak berulang dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!