Menyelesaikan Dua Jumlah II dengan Cekap - Tatasusunan Input Diisih

Masalah "Two Sum II - Input Array Is Sorted" ialah cabaran pengekodan klasik yang menguji pemahaman anda tentang tatasusunan dan manipulasi penunjuk. Ia juga merupakan peluang yang baik untuk mempamerkan penyelesaian yang elegan dan cekap. Mari kita selami masalah ini dan pecahkan pendekatan optimum untuk menyelesaikannya.

Pautan kepada masalah pada LeetCode

Pernyataan Masalah

Memandangkan tatasusunan 1-indeks nombor integer yang diisih dalam susunan tidak menurun, matlamat anda adalah untuk mencari dua nombor supaya jumlahnya sama dengan sasaran tertentu. Anda perlu mengembalikan indeks dua nombor ini sebagai tatasusunan [index1, index2] dengan 1 <= index1 < indeks2 <= nombor.panjang. Penyelesaiannya hendaklah menggunakan hanya ruang tambahan yang berterusan.

Kekangan

• Nombor tatasusunan diisih dalam susunan tidak menurun.
• Terdapat satu penyelesaian.
• Anda tidak boleh menggunakan elemen yang sama dua kali.
• Panjang tatasusunan input berjulat dari 2 hingga 30,000.
• Nilai dalam julat tatasusunan daripada −1000 hingga 1000.

Contoh Input dan Output

1. Input: nombor = [2,7,11,15], sasaran = 9
   
   Output: [1, 2]

2. Input: nombor = [2,3,4], sasaran = 6
   
   Output: [1, 3]

3. Input: nombor = [-1,0], sasaran = -1
   
   Output: [1, 2]

Pendekatan: Dua Petunjuk

Kekangan masalah—susunan tersusun dan penyelesaian tunggal—menjadikannya calon yang sempurna untuk teknik dua mata. Inilah sebabnya:

• Kecekapan: Dua penunjuk membolehkan kami melintasi tatasusunan dalam satu laluan (O(n) kerumitan masa).
• Ruang Malar: Kami mengelakkan struktur data tambahan, mematuhi keperluan masalah ruang tambahan yang berterusan.

Perlaksanaan

Di bawah ialah pelaksanaan JavaScript bagi pendekatan dua mata:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};






  
  
  Bagaimana Ia Berfungsi




Mulakan Dua Penunjuk:



leftPointer bermula pada permulaan tatasusunan.

rightPointer bermula pada penghujung tatasusunan.



Lelar Sehingga Mereka Bertemu:


Kira jumlah elemen di leftPointer dan rightPointer.
Jika jumlahnya sepadan dengan sasaran, kembalikan kedudukan 1 diindeks.
Jika jumlah lebih besar daripada sasaran, kurangkan Penunjuk kanan untuk mengurangkan jumlah.
Jika jumlah kurang daripada sasaran, naikkan Penunjuk kiri untuk menambah jumlah.



Kembalikan Indeks:

Setelah pasangan yang betul ditemui, gelung ditamatkan dan mengembalikan indeks.





  
  
  Contoh Panduan


Mari kita lihat contoh pertama:



Input: nombor = [2, 7, 11, 15], sasaran = 9


Permulaan: leftPointer = 0, rightPointer = 3




  
  
  Langkah Lelaran:



Kira nombor[0] nombor[3] = 2 15 = 17. 


Terlalu besar, kurangkan ke kananTuding ke 2.


Kira nombor[0] nombor[2] = 2 11 = 13. 


Masih terlalu besar, kurangkan ke kananTuding kepada 1.


Kira nombor[0] nombor[1] = 2 7 = 9. 


Padanan ditemui, kembali [1, 2].





  
  
  Perkara Utama




Pelarasan Berindeks 1: Masalahnya menentukan pengindeksan berasaskan 1, jadi kami menambah 1 pada kedua-dua penunjuk sebelum kembali.

Kes Tepi: Kekangan menjamin penyelesaian tunggal, jadi kami tidak perlu mengendalikan tatasusunan kosong atau berbilang padanan.

Pengoptimuman: Menggunakan pendekatan dua mata memastikan kami memenuhi kerumitan masa O(n) dan keperluan ruang yang berterusan.



  
  
  Kesimpulan


Kaedah dua penuding dengan elegan menyelesaikan masalah "Two Sum II - Input Array Is Sorted" dengan memanfaatkan sifat tersusun tatasusunan input. Ia merupakan teknik berkuasa yang bukan sahaja memastikan kecekapan tetapi juga mematuhi kekangan ruang, menjadikannya pendekatan yang sesuai untuk masalah yang sama. Selamat mengekod!


          

            
        
Atas ialah kandungan terperinci Menyelesaikan Dua Jumlah II dengan Cekap - Tatasusunan Input Diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!