Array និង String

មាតិកា

1. ប្លង់អង្គចងចាំ៖ ហេតុអ្វីការចូលតាម index លឿន
2. Array របស់ JavaScript ក្នុងជីវិតពិត
3. តម្លៃនៃប្រតិបត្តិការនីមួយៗ
4. មើលតម្លៃ៖ push, pop, shift, unshift
5. splice, slice និងការចម្លង
6. String គឺជា Array នៃតួអក្សរ (ស្ទើរតែ)
7. បច្ចេកទេសទី 1៖ Two Pointers
8. បច្ចេកទេសទី 2៖ Sliding Window
9. បច្ចេកទេសទី 3៖ Prefix Sums
10. បញ្ហាសម្ភាសន៍
11. រូបមន្ត៖ module arrays
12. សាកល្បងដោយខ្លួនឯង

1. ប្លង់អង្គចងចាំ៖ ហេតុអ្វីការចូលតាម index លឿន

អង្គចងចាំកុំព្យូទ័រគឺជាជួរវែងនៃប្រអប់ដែលមានលេខរៀង។ Array បុរាណ ស្នើសុំពីប្រព័ន្ធនូវប្លុកនៃប្រអប់ដែលនៅជាប់គ្នាស្រាប់ ហើយដាក់ធាតុមួយក្នុងប្រអប់នីមួយៗ។ ប្រសិនបើប្លុកចាប់ផ្តើមនៅអាសយដ្ឋាន 1000 ហើយធាតុនីមួយៗប្រើ 8 byte នោះ៖

index:    0      1      2      3      4
address:  1000   1008   1016   1024   1032
value:    [ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]

ដើម្បីអានធាតុ 3 កុំព្យូទ័រធ្វើនព្វន្តតែមួយប៉ុណ្ណោះ៖ 1000 + 3 * 8 = 1024 បន្ទាប់មកអានប្រអប់នោះ។ វាមិនមានបញ្ហាទេថា array មានប្រាំធាតុ ឬប្រាំលានធាតុ។ នោះជាហេតុផលដែលការអាន ឬសរសេរ arr[i] គឺ O(1)។

ប្លង់ដូចគ្នានេះពន្យល់អំពីចំណុចខ្សោយ៖

• ការបញ្ចូលនៅកណ្តាល មានន័យថារាល់ធាតុក្រោយចន្លោះត្រូវរំកិលដើម្បីបង្កើតកន្លែង៖ រហូតដល់ n ការរំកិល។
• ការលុបពីកណ្តាល ទុកប្រហោងមួយ ដូច្នេះរាល់ធាតុក្រោយវាត្រូវរំកិលថយក្រោយ៖ រហូតដល់ n ការរំកិល។
• ការលូតលាស់លើសចុង អាចត្រូវការប្លុកទំនេរធំជាងមុន ដូច្នេះ array ទាំងមូលត្រូវបានចម្លងទៅកន្លែងថ្មី។

ចងចាំរូបភាពនេះ។ ស្ទើរតែគ្រប់តម្លៃក្នុងជំពូកនេះមកពី "ប្រអប់ជាប់គ្នា ជាមួយអាសយដ្ឋាននព្វន្ត"។

2. Array របស់ JavaScript ក្នុងជីវិតពិត

JavaScript លាក់ព័ត៌មានលម្អិតភាគច្រើន។ Array របស់ JavaScript គឺជាបញ្ជីដែលអាចប្តូរទំហំបាន៖ អ្នកអាច push បានច្រើនតាមចិត្តដោយមិនចាំបាច់ជ្រើសទំហំ។ នៅពីក្រោយ engine រក្សាប្លុកអង្គចងចាំពិតប្រាកដសម្រាប់វា ហើយនៅពេលអ្នកលើសប្លុក វាបែងចែកប្លុកធំជាងមុន (ជាធម្មតាធំជាងប្លុកចាស់បន្តិច) ហើយចម្លងធាតុទៅ។

ការចម្លងមើលទៅថ្លៃ ប៉ុន្តែ engine ធ្វើវាតែកម្រៗប៉ុណ្ណោះ ពីព្រោះប្លុកថ្មីនីមួយៗធំជាងប្លុកមុនច្រើន។ ពេលរាយលើ push ជាច្រើន តម្លៃជាមធ្យមនៃ push មួយនៅតែជា O(1)។ គំនិតនេះហៅថាតម្លៃ amortized៖ ជំហានថ្លៃម្តងម្កាល ដែលត្រូវបានបង់ដោយជំហានថោកជាច្រើន។

ព័ត៌មានលម្អិតស្មោះត្រង់ខ្លះអំពី JavaScript ជាពិសេស៖

• Array អាចផ្ទុកប្រភេទចម្រុះ៖ [1, "two", { three: 3 }]។ Engine លឿនបំផុតនៅពេលធាតុទាំងអស់ជាតម្លៃប្រភេទដូចគ្នា (ឧទាហរណ៍ integer តូចៗទាំងអស់) ពីព្រោះវាអាចខ្ចប់ពួកវាយ៉ាងតឹងរ៉ឹង។
• ការសរសេរឆ្ងាយហួសចុង ដូចជា arr[1000000] = 1 លើ array ខ្លី បង្កើត array sparse ដែលមានប្រហោង។ Engine ប្តូរទៅការតំណាងយឺតជាងសម្រាប់ពួកវា។ ចៀសវាងវា។
• សម្រាប់ការងារតែលេខ មាន typed array ដូចជា Float64Array និង Uint8Array៖ ទំហំថេរ ប្រភេទលេខមួយ តូចល្មមខ្លាំង។ អ្នកឃើញពួកវាក្នុងក្រាហ្វិក សំឡេង និងការ parse ឯកសារ binary។
• arr.length គឺជាតម្លៃដែលបានរក្សាទុក។ ការអានវាគឺ O(1) ដូច្នេះមិនចាំបាច់ cache វាក្នុង variable "ដើម្បីល្បឿន" ទេ។

សម្រាប់ស៊េរីនេះ សូមគិតថា array របស់ JavaScript គឺជា "dynamic array"៖ ការអានតាម index គឺ O(1) ការបន្ថែម ឬលុបនៅ ចុង គឺ O(1) ហើយអ្វីៗនៅ ខាងមុខ ឬកណ្តាល គឺ O(n)។

3. តម្លៃនៃប្រតិបត្តិការនីមួយៗ

នេះគឺជាប្រតិបត្តិការដែលអ្នកប្រើច្រើនបំផុត ជាមួយតម្លៃ Big-O របស់វា៖

ច្បាប់ជាក់ស្តែងដែលចេញពីតារាង៖

• ការធ្វើការនៅ ចុង នៃ array គឺថោក ការធ្វើការនៅ ខាងមុខ មិនថោកទេ។ ប្រសិនបើអ្នកត្រូវការជួរ "ចូលមុនចេញមុន" array ជាមួយ shift គឺជាអន្ទាក់សម្រាប់ទិន្នន័យធំ។ យើងជួសជុលរឿងនោះក្នុងជំពូកទី 5។
• ការ chain map, filter និង reduce គឺមិនអីទេ៖ នីមួយៗជាការឆ្លងកាត់មួយដង ហើយបីដងនៅតែជា O(n)។ Loop ក្នុង loop ឬ method ស្វែងរកក្នុង loop គឺជាអ្វីដែលបំប្លែង O(n) ទៅជា O(n^2)។

4. មើលតម្លៃ៖ push, pop, shift, unshift

តោះវាស់។ Script នេះធ្វើប្រតិបត្តិការ 100,000 សម្រាប់ប្រភេទនីមួយៗ។ (បង្កើតឯកសារសាកល្បង ឧទាហរណ៍ scratch.ts ហើយដំណើរការវាជាមួយ npx tsx scratch.ts។)

function timeIt(label: string, fn: () => void) {
  const start = performance.now();
  fn();
  console.log(label.padEnd(8), (performance.now() - start).toFixed(1), "ms");
}

const N = 100_000;

const a: number[] = [];
timeIt("push", () => {
  for (let i = 0; i < N; i++) a.push(i);
});

const b: number[] = [];
timeIt("unshift", () => {
  for (let i = 0; i < N; i++) b.unshift(i);
});

const c = Array.from({ length: N }, (_, i) => i);
timeIt("pop", () => {
  while (c.length > 0) c.pop();
});

const d = Array.from({ length: N }, (_, i) => i);
timeIt("shift", () => {
  while (d.length > 0) d.shift();
});

នៅលើកុំព្យូទ័រយួរដៃមួយ លទ្ធផលគឺ៖

push     2.0 ms
unshift  633.8 ms
pop      0.6 ms
shift    672.8 ms

លេខរបស់អ្នកនឹងខុសគ្នា ប៉ុន្តែលំនាំនឹងមិនខុសទេ៖ ប្រតិបត្តិការនៅចុងទាំងពីរចំណាយពេលពីរបីមីលីវិនាទី ហើយប្រតិបត្តិការនៅខាងមុខទាំងពីរចំណាយពេលយូរជាងរាប់រយដង។ unshift និង shift នីមួយៗរំកិលរហូតដល់ 100,000 ធាតុ ដូច្នេះ 100,000 ដងនៃវាចំណាយប្រហែល 100,000 * 100,000 / 2 ការរំកិលធាតុ។ នោះគឺ O(n^2) សម្រាប់ loop ទាំងមូល។

(Engine ទំនើបមានល្បិចឆ្លាតវៃដែលជួនកាលធ្វើឲ្យ shift ថោកជាងនៅលើ array តូចៗ។ កុំពឹងផ្អែកលើវា។ សន្មត់ O(n)។)

វិធីបុរាណដែលរឿងនេះខាំក្នុងកូដពិតគឺ work queue ដែលសរសេរជាមួយ array៖

const queue: string[] = ["job1", "job2", "job3"];
queue.push("job4");        // add to the back: cheap
const next = queue.shift(); // take from the front: O(n)!
console.log(next, queue);   // job1 [ 'job2', 'job3', 'job4' ]

ជាមួយ job បី វាមិនអីទេ។ ជាមួយ job មួយលានក្នុង queue រាល់ shift រំកិលធាតុមួយលាន។ ចងចាំរឿងនេះរហូតដល់ជំពូកទី 5។

5. splice, slice និងការចម្លង

splice គឺជាកាំបិតពហុមុខងារសម្រាប់ផ្លាស់ប្តូរកណ្តាលនៃ array។ វា mutate array៖ វាលុបធាតុ ហើយបញ្ចូលធាតុថ្មីជំនួសជាជម្រើស ហើយវា return ធាតុដែលបានលុប។

const arr: (number | string)[] = [1, 2, 3, 4, 5];
const removed = arr.splice(1, 2, "a", "b", "c");
//                         ^  ^   items to insert
//                         |  how many to remove
//                         start index
console.log(removed); // [ 2, 3 ]
console.log(arr);     // [ 1, 'a', 'b', 'c', 4, 5 ]

តម្លៃគឺ O(n) ពីព្រោះកន្ទុយ (4, 5 នៅទីនេះ) ត្រូវរំកិលទៅទីតាំងថ្មី។ ការលុបតាម index arr.splice(i, 1) គឺដូចគ្នា។

slice មិន mutate ទេ។ វាចម្លងចន្លោះមួយទៅ array ថ្មី៖

const nums = [10, 20, 30, 40, 50];
console.log(nums.slice(1, 3));  // [ 20, 30 ]   (end index is excluded)
console.log(nums.slice(-2));    // [ 40, 50 ]   (last two)
console.log(nums);              // [ 10, 20, 30, 40, 50 ] unchanged

slice គឺ O(k) ដែល k ជាចំនួនធាតុដែលបានចម្លង។ Spread [...nums] ចម្លង array ទាំងមូលក្នុង O(n)។

ឧបទ្ទវហេតុទូទៅ៖ ការចម្លងក្នុង loop។ នេះមើលទៅគ្មានគ្រោះថ្នាក់៖

function sumOfSuffixes(nums: number[]): number {
  let total = 0;
  for (let i = 0; i < nums.length; i++) {
    const rest = nums.slice(i);            // O(n) copy every time
    total += rest.reduce((a, b) => a + b, 0);
  }
  return total;
}

វាមានការងារពីរដងក្នុង loop ដូច្នេះវាគឺ O(n^2)។ នៅពេលអ្នកឃើញ slice, concat, [...arr] ឬ includes នៅក្នុងតួ loop សូមឈប់ ហើយរាប់។

ចងចាំផងដែរថា array គឺជា object ដូច្នេះការ assign ចម្លង reference មិនមែនខ្លឹមសារទេ៖

const original = [1, 2, 3];
const alias = original;       // same array, two names
const copy = [...original];   // a real copy

alias.push(4);
console.log(original); // [ 1, 2, 3, 4 ]
console.log(copy);     // [ 1, 2, 3 ]

6. String គឺជា Array នៃតួអក្សរ (ស្ទើរតែ)

String មើលទៅដូច array នៃតួអក្សរ៖ វាមាន length ហើយ text[0] ផ្តល់តួអក្សរដំបូង។ ការអានតាម index ក៏ជា O(1) ដែរ។ ប៉ុន្តែមានភាពខុសគ្នាសំខាន់ៗ។

String គឺ immutable។ អ្នកមិនអាចផ្លាស់ប្តូរតួអក្សរនៅនឹងកន្លែងបានទេ៖

let word = "cat";
word[0] = "b";        // silently does nothing (an error in strict mode)
console.log(word);    // cat
word = "b" + word.slice(1); // build a new string instead
console.log(word);    // bat

រាល់ "ការផ្លាស់ប្តូរ" បង្កើត string ថ្មី ហើយចំណាយ O(n) ដើម្បីចម្លង។ នោះធ្វើឲ្យការសាងសង់ string វែងដោយ += ក្នុង loop អាចជា O(n^2) តាមទ្រឹស្តី (engine ទំនើប optimize ករណីសាមញ្ញ ប៉ុន្តែអ្នកមិនអាចពឹងផ្អែកលើវាសម្រាប់គ្រប់លំនាំទេ)។ ទម្លាប់សុវត្ថិភាព៖ ប្រមូលបំណែកក្នុង array ហើយ join ម្តងនៅចុងបញ្ចប់។

const parts: string[] = [];
for (let i = 0; i < 5; i++) parts.push(`row${i}`);
console.log(parts.join(",")); // row0,row1,row2,row3,row4

ការបំបែក string ទៅជា array នៃតួអក្សរ ធ្វើការលើ array ហើយភ្ជាប់ត្រឡប់មកវិញ គឺជាវិធីធម្មតាដើម្បី "កែ" អត្ថបទ៖

console.log("a-b-c".split("-"));        // [ 'a', 'b', 'c' ]
console.log("hello".split("").reverse().join("")); // olleh

តួអក្សរមិនតែងតែមានទីតាំងតែមួយទេ។ String របស់ JavaScript គឺជាលំដាប់នៃឯកតា 16-bit (UTF-16)។ អក្សរភាគច្រើនប្រើឯកតាមួយ ប៉ុន្តែ emoji និងនិមិត្តសញ្ញាផ្សេងទៀតប្រើពីរ ដែលធ្វើឲ្យកូដឆោតល្ងង់ខូច៖

console.log("hello".length);   // 5
console.log("😀".length);       // 2   (one visible symbol, two units)
console.log([..."héllo😀"].length); // 6  (spread iterates whole symbols)

សម្រាប់បញ្ហាសម្ភាសន៍ "សន្មត់អក្សរអង់គ្លេសតូច" គឺជាច្បាប់ធម្មតា ហើយ .length គឺមិនអីទេ។ សម្រាប់អត្ថបទអ្នកប្រើពិត ដូចជាឈ្មោះជាភាសាខ្មែរ ឬអត្ថបទដែលមាន emoji សូមប្រើ spread [...text] ឬ Intl.Segmenter ដើម្បីរាប់អ្វីដែលអ្នកប្រើឃើញពិតប្រាកដ។ កុំបញ្ច្រាស ឬកាត់អត្ថបទបែបនេះដោយនព្វន្ត index។

7. បច្ចេកទេសទី 1៖ Two Pointers

ក្បួនដោះស្រាយ two-pointer រក្សា index ពីរក្នុង array ដូចគ្នា ហើយផ្លាស់ទីវាតាមច្បាប់សាមញ្ញ ដោយជំនួស loop ដែលដាក់ជាន់គ្នាជាមួយការឆ្លងកាត់តែមួយ។ មានរូបរាងសំខាន់ពីរ៖

• ចុងទល់មុខ៖ left ចាប់ផ្តើមនៅ 0 right នៅ index ចុងក្រោយ ហើយពួកវាផ្លាស់ទីឆ្ពោះរកគ្នា។
• ទិសដៅដូចគ្នា៖ pointer read លឿនស្កេន ហើយ pointer write យឺតសម្គាល់កន្លែងដែលធាតុល្អបន្ទាប់ត្រូវទៅ។

ចុងទល់មុខ៖ បញ្ច្រាសនៅនឹងកន្លែង

function reverseInPlace<T>(items: T[]): T[] {
  let left = 0;
  let right = items.length - 1;
  while (left < right) {
    [items[left], items[right]] = [items[right], items[left]];
    left++;
    right--;
  }
  return items;
}

console.log(reverseInPlace([1, 2, 3, 4, 5])); // [ 5, 4, 3, 2, 1 ]

នេះគឺ O(n) ពេលវេលា និង O(1) លំហបន្ថែម៖ វាប្តូរគូពីខាងក្រៅចូលខាងក្នុង ហើយមិនដែលបែងចែក array ទីពីរឡើយ។

ចុងទល់មុខ៖ palindrome

Palindrome អានដូចគ្នាទាំងពីរទិស។ មិនគិតពីវណ្ណយុត្តិ និងអក្សរធំតូច៖

function isPalindrome(text: string): boolean {
  const clean = text.toLowerCase().replace(/[^a-z0-9]/g, "");
  let left = 0;
  let right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("hello"));                          // false

ចុងទល់មុខ៖ two sum ក្នុង array ដែលបានតម្រៀប

ដោយមាន array ដែលបានតម្រៀប រកធាតុពីរដែលបូកស្មើ target។ Brute force ពិនិត្យគ្រប់គូ៖ O(n^2)។ ដោយសារ array ត្រូវបានតម្រៀប យើងអាចធ្វើបានល្អជាងនេះ។ មើលធាតុតូចបំផុត និងធំបំផុត៖

• ប្រសិនបើផលបូករបស់ពួកវាតូចពេក វិធីតែមួយគត់ដើម្បីបង្កើនវាគឺផ្លាស់ទី left ទៅស្តាំ (លេខតូចធំជាងមុន)។
• ប្រសិនបើផលបូករបស់ពួកវាធំពេក វិធីតែមួយគត់ដើម្បីបន្ថយវាគឺផ្លាស់ទី right ទៅឆ្វេង។

function twoSumSorted(
  sorted: number[],
  target: number
): [number, number] | null {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10)); // [ 2, 3 ]  (4 + 6)
console.log(twoSumSorted([1, 2], 10));              // null

តាមដានការហៅលើកដំបូង៖ 1 + 11 = 12 ធំពេក ដូច្នេះ right ផ្លាស់ទីទៅ 8។ 1 + 8 = 9 តូចពេក ដូច្នេះ left ផ្លាស់ទីទៅ 3។ 3 + 8 = 11 ធំពេក ដូច្នេះ right ផ្លាស់ទីទៅ 6។ 3 + 6 = 9 តូចពេក ដូច្នេះ left ផ្លាស់ទីទៅ 4។ 4 + 6 = 10៖ រកឃើញ នៅ index 2 និង 3។ ជំហាននីមួយៗបោះបង់បេក្ខជនមួយជាស្ថាពរ ដូច្នេះរឿងទាំងមូលគឺ O(n)។

ទិសដៅដូចគ្នា៖ លុបធាតុស្ទួនពី array ដែលបានតម្រៀប

ទិន្នន័យដែលបានតម្រៀបរក្សាធាតុស្ទួននៅជាប់គ្នា។ Pointer write យឺតសម្គាល់ចុងនៃបុព្វបទដែលមិនស្ទួន ហើយ pointer read លឿនស្កេន៖

function removeDuplicatesSorted(sorted: number[]): number {
  if (sorted.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < sorted.length; read++) {
    if (sorted[read] !== sorted[write - 1]) {
      sorted[write] = sorted[read];
      write++;
    }
  }
  return write; // the count of unique items
}

const data = [1, 1, 2, 2, 2, 3];
const count = removeDuplicatesSorted(data);
console.log(count, data.slice(0, count)); // 3 [ 1, 2, 3 ]

វាកែប្រែ array នៅនឹងកន្លែង ក្នុង O(n) ពេលវេលា និង O(1) លំហ។ គំនិត "សរសេរជាន់នៅពេលស្កេន" នេះនឹងត្រឡប់មកវិញក្នុង sorting និង partitioning។

8. បច្ចេកទេសទី 2៖ Sliding Window

បញ្ហាជាច្រើនសួរអំពី ចន្លោះជាប់គ្នា (subarray ឬ substring) ដែលបំពេញលក្ខខណ្ឌមួយ។ Brute force ពិនិត្យគ្រប់ចន្លោះ។ Sliding window រក្សាចន្លោះតែមួយ ហើយផ្លាស់ទីវាទៅមុខ ដោយបន្ថែមធាតុថ្មីនៅគែមស្តាំ និងទម្លាក់ធាតុចាស់នៅឆ្វេង ហើយធ្វើបច្ចុប្បន្នភាពចម្លើយបន្តិចម្តងៗ។

Window ទំហំថេរ៖ ផលបូកល្អបំផុតនៃធាតុ k

រកផលបូកធំបំផុតនៃលេខជាប់គ្នា k។ វិធីយឺតបូកលេខ k សម្រាប់ចំណុចចាប់ផ្តើមនីមួយៗ៖ O(n * k)។ វិធី window បូកធាតុដែលចូល ហើយដកធាតុដែលចេញ៖

function maxSumWindow(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) throw new RangeError("k out of range");
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]; // add the new item, drop the old one
    if (sum > best) best = sum;
  }
  return best;
}

console.log(maxSumWindow([2, 1, 5, 1, 3, 2], 3)); // 9  (5 + 1 + 3)

ដើរកាត់វា៖ window ដំបូង [2, 1, 5] បូកបាន 8។ រំកិលទៅ [1, 5, 1] ផ្តល់ 8 + 1 - 2 = 7។ បន្ទាប់មក [5, 1, 3] ផ្តល់ 7 + 3 - 1 = 9។ បន្ទាប់មក [1, 3, 2] ផ្តល់ 9 + 2 - 5 = 6។ ល្អបំផុតគឺ 9។ ជំហាននីមួយៗគឺ O(1) ដូច្នេះសរុបគឺ O(n) មិនថា k ធំប៉ុនណាឡើយ។

Window ទំហំអថេរ៖ substring វែងបំផុតដែលគ្មានតួអក្សរស្ទួន

រកប្រវែងនៃ substring វែងបំផុតដែលគ្មានតួអក្សរស្ទួន។ Window លូតលាស់នៅខាងស្តាំរាល់ជំហាន។ នៅពេលវានឹងមានតួអក្សរស្ទួន គែមឆ្វេងលោតទៅមុខហួសច្បាប់ចម្លងមុននៃតួអក្សរនោះ។ Map ចងចាំ index ចុងក្រោយនៃតួអក្សរនីមួយៗ (ជំពូកទី 3 ពន្យល់ Map ពេញលេញ)៖

function longestUniqueSubstring(text: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0;
  let best = 0;
  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= start) start = prev + 1;
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

console.log(longestUniqueSubstring("abcabcbb")); // 3  ("abc")
console.log(longestUniqueSubstring("bbbbb"));    // 1
console.log(longestUniqueSubstring("pwwkew"));   // 3  ("wke")
console.log(longestUniqueSubstring("abba"));     // 2

ការពិនិត្យ prev >= start មានសារៈសំខាន់។ ក្នុង "abba" នៅពេលយើងដល់ a ចុងក្រោយ ទីតាំងចុងក្រោយរបស់វា (0) គឺនៅ ក្រៅ window រួចហើយ ដូច្នេះ start មិនត្រូវផ្លាស់ទីថយក្រោយទេ។ បើគ្មានការពិនិត្យនោះ អ្នកនឹងទទួលបានចម្លើយខុសគឺ 3 សម្រាប់ input នេះ។ តួអក្សរនីមួយៗចូល និងចេញពី window យ៉ាងច្រើនម្តង ដូច្នេះតម្លៃគឺ O(n)។

ពេលណាត្រូវប្រើ sliding window៖ សំណួរនិយាយថា "subarray" ឬ "substring" សួររកមួយវែងបំផុត ខ្លីបំផុត ឬល្អបំផុត ហើយលក្ខខណ្ឌអាចត្រូវបានពិនិត្យដោយធ្វើបច្ចុប្បន្នភាព counter ពីរបីនៅពេលធាតុចូល ឬចេញ។

9. បច្ចេកទេសទី 3៖ Prefix Sums

សន្មត់ថាអ្នកឆ្លើយសំណួររាប់ពាន់នៃទម្រង់ "តើផលបូកនៃធាតុពី index i ដល់ index j ជាអ្វី?" លើ array ដូចគ្នា។ ការបូកចន្លោះឡើងវិញរាល់ពេលចំណាយ O(n) ក្នុងមួយសំណួរ។

Array prefix sum ធ្វើការបូកម្តង។ prefix[k] រក្សាផលបូកនៃធាតុ k ដំបូង។ បន្ទាប់មកផលបូកចន្លោះណាមួយគឺជាការដកតែមួយ៖

nums:    [ 3, 1, 4, 1, 5, 9, 2, 6 ]
prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
          ^                       ^
          prefix[0] = 0 (empty)   prefix[8] = sum of all 8 items

ផលបូកនៃ nums[from..to] (រួមទាំងពីរ) គឺ prefix[to + 1] - prefix[from]៖

function buildPrefix(nums: number[]): number[] {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return prefix;
}

function rangeSum(prefix: number[], from: number, to: number): number {
  return prefix[to + 1] - prefix[from];
}

const prefix = buildPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(prefix);                  // [ 0, 3, 4, 8, 9, 14, 23, 25, 31 ]
console.log(rangeSum(prefix, 2, 5));  // 19  (4 + 1 + 5 + 9)
console.log(rangeSum(prefix, 0, 7));  // 31  (everything)

ការសាងសង់ចំណាយ O(n) ម្តង។ បន្ទាប់ពីនោះ រាល់ query គឺ O(1)។ នេះគឺជាការដោះដូរពេលវេលាជាមួយអង្គចងចាំពីជំពូកទី 1៖ array បន្ថែមមួយនៃលេខ n + 1។

0 នៅខាងមុខមិនមែនជាល្បិចសម្រាប់បង្ហាញទេ។ វាអនុញ្ញាតឲ្យចន្លោះដែលចាប់ផ្តើមនៅ index 0 ដំណើរការជាមួយរូបមន្តដូចគ្នា ដោយគ្មានករណីពិសេស។ កំហុស off-by-one កើតឡើងជាប្រចាំជាមួយចន្លោះ ដូច្នេះរក្សាអនុសញ្ញាឲ្យថេរ៖ prefix[k] គឺជាផលបូកនៃធាតុ k ដំបូង។

តើអ្នកជួបរឿងនេះនៅកន្លែងធ្វើការត្រង់ណា? ផ្ទាំងវិភាគ ("ចំណូលរវាងកាលបរិច្ឆេទពីរ" នៅពេលទិន្នន័យជា array ប្រចាំថ្ងៃ) ការដំណើរការរូបភាព ("ផលបូកនៃ pixel ក្នុងចតុកោណ" កំណែ 2D) និងជួរឈរ "ផលបូកដែលកំពុងដំណើរការ" ណាមួយក្នុង spreadsheet។ គំនិតដូចគ្នាដំណើរការជាមួយការរាប់ ផលគុណ និង XOR។

10. បញ្ហាសម្ភាសន៍

Move zeroes

ដោយមាន array ផ្លាស់ទីលេខសូន្យទាំងអស់ទៅចុង ខណៈរក្សាលំដាប់នៃធាតុផ្សេងទៀត នៅនឹងកន្លែង។ ឧទាហរណ៍៖ [0, 1, 0, 3, 12] ក្លាយជា [1, 3, 12, 0, 0]។

Two pointers ទិសដៅដូចគ្នា៖ read ស្កេនគ្រប់ធាតុ write សម្គាល់កន្លែងដែលធាតុមិនមែនសូន្យបន្ទាប់ត្រូវទៅ។ ការប្តូរធាតុមិនមែនសូន្យចូលកន្លែង បញ្ជូនលេខសូន្យដែលវាជំនួសឆ្ពោះទៅក្រោយ៖

function moveZeroes(nums: number[]): number[] {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

console.log(moveZeroes([0, 1, 0, 3, 12])); // [ 1, 3, 12, 0, 0 ]

នេះគឺ O(n) ពេលវេលា O(1) លំហ។ ចម្លើយខុសដែលត្រូវចៀសវាងគឺ splice លេខសូន្យនីមួយៗចេញ ហើយ push លេខសូន្យថ្មីចូល ដែលចំណាយ O(n) ក្នុងមួយលេខសូន្យ និង O(n^2) សរុប។

របៀបនិយាយអំពីវា

សម្រាប់បញ្ហានីមួយៗ អនុវត្តការនិយាយភាពស្មុគស្មាញឲ្យឮៗ៖

11. រូបមន្ត៖ module arrays

បន្ថែម src/arrays.ts ទៅ algolab ជាមួយអ្វីៗទាំងអស់ពីជំពូកនេះ៖

// src/arrays.ts

// ---- two pointers ----

export function reverseInPlace<T>(items: T[]): T[] {
  let left = 0;
  let right = items.length - 1;
  while (left < right) {
    [items[left], items[right]] = [items[right], items[left]];
    left++;
    right--;
  }
  return items;
}

export function isPalindrome(text: string): boolean {
  const clean = text.toLowerCase().replace(/[^a-z0-9]/g, "");
  let left = 0;
  let right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false;
    left++;
    right--;
  }
  return true;
}

export function twoSumSorted(
  sorted: number[],
  target: number
): [number, number] | null {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

export function removeDuplicatesSorted(sorted: number[]): number {
  if (sorted.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < sorted.length; read++) {
    if (sorted[read] !== sorted[write - 1]) {
      sorted[write] = sorted[read];
      write++;
    }
  }
  return write;
}

export function moveZeroes(nums: number[]): number[] {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

// ---- sliding window ----

export function maxSumWindow(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) throw new RangeError("k out of range");
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];
    if (sum > best) best = sum;
  }
  return best;
}

export function longestUniqueSubstring(text: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0;
  let best = 0;
  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= start) start = prev + 1;
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

// ---- prefix sums ----

export function buildPrefix(nums: number[]): number[] {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return prefix;
}

export function rangeSum(
  prefix: number[],
  from: number,
  to: number
): number {
  return prefix[to + 1] - prefix[from];
}

ឥឡូវ test ក្នុង src/arrays.test.ts៖

// src/arrays.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  reverseInPlace,
  isPalindrome,
  twoSumSorted,
  removeDuplicatesSorted,
  moveZeroes,
  maxSumWindow,
  longestUniqueSubstring,
  buildPrefix,
  rangeSum,
} from "./arrays.ts";

test("two pointers", () => {
  assert.deepEqual(reverseInPlace([1, 2, 3]), [3, 2, 1]);
  assert.equal(isPalindrome("A man, a plan, a canal: Panama"), true);
  assert.equal(isPalindrome("hello"), false);
  assert.deepEqual(twoSumSorted([1, 3, 4, 6, 8, 11], 10), [2, 3]);
  assert.equal(twoSumSorted([1, 2], 10), null);
  const d = [1, 1, 2, 2, 3];
  assert.equal(removeDuplicatesSorted(d), 3);
  assert.deepEqual(d.slice(0, 3), [1, 2, 3]);
  assert.deepEqual(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0]);
});

test("sliding window", () => {
  assert.equal(maxSumWindow([2, 1, 5, 1, 3, 2], 3), 9);
  assert.throws(() => maxSumWindow([1], 2), RangeError);
  assert.equal(longestUniqueSubstring("abcabcbb"), 3);
  assert.equal(longestUniqueSubstring("abba"), 2);
});

test("prefix sums", () => {
  const p = buildPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
  assert.equal(rangeSum(p, 2, 5), 19);
  assert.equal(rangeSum(p, 0, 7), 31);
});

ដំណើរការ npm test។ ឥឡូវអ្នកគួរឃើញ test ជាប់ចំនួន 6 (3 ពីជំពូកទី 1 និង 3 ថ្មី) និង # fail 0។

បង្កើតឯកសារថ្មី demo2.ts ដើម្បីមើល window ឈ្នះ brute force៖

import { time } from "./src/bench.ts";
import { maxSumWindow } from "./src/arrays.ts";

const big = Array.from({ length: 50_000 }, (_, i) => (i * 37) % 101);
const k = 1000;

const brute = time(() => {
  let best = -Infinity;
  for (let i = 0; i + k <= big.length; i++) {
    let s = 0;
    for (let j = i; j < i + k; j++) s += big[j];
    if (s > best) best = s;
  }
  return best;
}, "brute force");

const windowed = time(() => maxSumWindow(big, k), "sliding window");

console.log(brute.label.padEnd(16), brute.ms.toFixed(1), "ms"); // about 30 ms
console.log(windowed.label.padEnd(16), windowed.ms.toFixed(2), "ms"); // about 0.6 ms
console.log("same answer:", brute.result === windowed.result); // true

ចម្លើយទាំងពីរតែងតែស្មើគ្នា។ កំណែ window ជាធម្មតាលឿនជាងរាប់សិបដង ហើយគម្លាតកើនឡើងជាមួយ k។

12. សាកល្បងដោយខ្លួនឯង

1. គណនាតម្លៃប្រតិបត្តិការ។ សម្រាប់នីមួយៗ សរសេរ Big-O៖ (a) arr.at(-1); (b) arr.unshift(0); (c) arr.splice(0, 1); (d) [...arr, x] ក្នុង loop ដែលដំណើរការ n ដង; (e) str.split("").reverse().join("")។
2. បញ្ចូល array ដែលបានតម្រៀបពីរចូលគ្នា។ សរសេរ mergeSorted(a, b) ដែល return array មួយដែលបានតម្រៀប ដោយប្រើ pointer មួយក្នុងមួយ input។ វាគួរចំណាយ O(n + m) ពេលវេលា។ (នេះក៏ជាបេះដូងនៃ merge sort ក្នុងជំពូកទី 8 ដែរ។)
3. ការេនៃ array ដែលបានតម្រៀប។ ដោយមាន array ដែលបានតម្រៀបដែលអាចមានលេខអវិជ្ជមាន ដូចជា [-4, -1, 0, 3, 10] return ការេតាមលំដាប់តម្រៀប៖ [0, 1, 9, 16, 100]។ ធ្វើវាក្នុង O(n) ជាមួយ two pointers ផ្លាស់ទីចូលពីចុងទាំងពីរ ដោយបំពេញលទ្ធផលពីក្រោយ។ ហេតុអ្វី map ធម្មតាបន្ទាប់មក sort ចំណាយច្រើនជាង?
4. Subarray ខ្លីបំផុតដែលមានផលបូកធំគ្រប់គ្រាន់។ ដោយមានលេខវិជ្ជមាន និងគោលដៅ return ប្រវែងនៃ subarray ជាប់គ្នាខ្លីបំផុតដែលផលបូករបស់វាយ៉ាងហោចណាស់ស្មើគោលដៅ (ឬ 0 ប្រសិនបើគ្មាន)។ សម្រាប់ [2, 3, 1, 2, 4, 3] និងគោលដៅ 7 ចម្លើយគឺ 2 (subarray [4, 3])។ គន្លឹះ៖ sliding window ទំហំអថេរ។
5. បែបសម្ភាសន៍៖ ផលគុណនៃអ្វីៗផ្សេងទៀត។ ដោយមាន nums return array ដែលធាតុ i គឺជាផលគុណនៃលេខទាំងអស់ លើកលែង nums[i] ដោយមិនប្រើការចែក។ សម្រាប់ [1, 2, 3, 4] ចម្លើយគឺ [24, 12, 8, 6]។ គន្លឹះ៖ សាងសង់ prefix product និង suffix product។
6. បែបសម្ភាសន៍៖ ផលបូក subarray ស្មើ k។ រាប់ subarray ជាប់គ្នាដែលបូកបាន k។ សម្រាប់ [1, 2, 3] ជាមួយ k = 3 ចម្លើយគឺ 2 ([1, 2] និង [3])។ ជាដំបូងធ្វើកំណែ O(n^2) ជាមួយ rangeSum; បន្ទាប់មកគិតអំពីរបៀបដែល Map នៃ prefix sum មុនៗ (មកក្នុងជំពូកទី 3) ធ្វើឲ្យវាក្លាយជា O(n)។

Array ផ្តល់ល្បឿនតាមទីតាំងដល់អ្នក ប៉ុន្តែពួកវាតស៊ូជាមួយ "រកតាមតម្លៃ"។ សម្រាប់រឿងនោះ យើងត្រូវការរចនាសម្ព័ន្ធដែលលោតត្រង់ទៅចម្លើយ។ បន្ទាប់គឺ Hash Map និង Set ដែលអ្នកនឹងរកឃើញថា Map និង Set សម្រេចបាន O(1) lookup យ៉ាងដូចម្តេច ហើយសាងសង់ class HashMap ផ្ទាល់ខ្លួនដើម្បីមើលវាដោយភ្នែកខ្លួនឯង។