[演算法筆記] Two Pointer & Prefix sum

演算法系列文

[Array & String]
- Sliding window
- Two Pointer & Prefix sum

[Hashing]

Two Pointer 算是自己比較熟悉的題型，所以這邊不會琢磨太多，但還是想筆記一下 two pointer 延伸出來的變化題，Two pointer 會比暴力解法的 O(n2) 效率好很多

🔖 文章索引

1. Classic Two Pointer
2. Two Pointer on two iterables
3. Prefix sum

Key Point

• 適用情境: array, string
• 題目是數字陣列通常為已 “排序”

Classic Two Pointer

Start the pointers L=0,R=input.length — 1at the edges of the input. Move them towards each other until they meet.

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. left++
            2. right--
            3. Both left++ and right--

耳熟能詳的題目例如

代表題

• 判斷字串 “abcdcba”, or “racecar” 是否為 palindrome (125. Valid Palindrome)
• 已經排序過的 Two Sum numbers = [2,7,11,15], target = 9 (167. Two Sum II — Input Array Is Sorted)

Two Pointer on two iterables

i=0,j=0Move along both inputs simultaneously until all elements have been checked.

Key Point

• 適用情境: 兩個 array 或 兩個字串
• 時間複雜度: Big O(n+m) if n = arr1.length and m = arr2.length

function fn(arr1, arr2):
    i = j = 0
    while i < arr1.length AND j < arr2.length:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. i++
            2. j++
            3. Both i++ and j++

    // Step 4: make sure both iterables are exhausted
    // Note that only one of these loops would run
    while i < arr1.length:
        Do some logic here depending on the problem
        i++

    while j < arr2.length:
        Do some logic here depending on the problem
        j++

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

判斷是否為子序列 (392. Is Subsequence)

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */

/**
 * Example 1
 * Input: s = "abc", t = "ahbgdc"
 * Output: true


 * Example 2
 * Input: s = "axc", t = "ahbgdc"
 * Output: false
*/

var isSubsequence = function(s, t) {
    if (s.length > t.length) return false;
    
    let i = 0;
    let j = 0;
    while(j<t.length){
        if(s[i] === t[j]){
            i++
        }
        j++
    }
    return i === s.length
};

Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted.

合併兩個排序過的 array (變形題 88. Merge Sorted Array )

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */

/**
 * Example 1
 * Input: arr1 = [1,4,7,10], arr2 = [3,5,6]
 * Output: [1,3,4,5,6,7,10]
*/

var combine = function(arr1, arr2) {
    // ans is the answer
    let ans = [];
    let i = 0, j = 0;
    
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            ans.push(arr1[i]);
            i++;
        } else {
            ans.push(arr2[j]);
            j++;
        }
    }
    
    while (i < arr1.length) {
        ans.push(arr1[i]);
        i++;
    }
    
    while (j < arr2.length) {
        ans.push(arr2[j]);
        j++;
    }
    
    return ans;
}

其他代表題

• 給定排序過字串 nums = [-4,-1,0,3,10]，平方後回傳排序後結果 [0,1,9,16,100]。(977. Squares of a Sorted Array)

Prefix sum

When a subarray starts at index 0, it is considered a "prefix" of the array. A prefix sum represents the sum of all prefixes. (1480. Running Sum of 1d Array)

Key Point

• 適用情境: whenever a problem involves sums of a subarray.
• 適用資料結構: arrays (of numbers)
• 時間複雜度: 𝑂(𝑛)
• 題目是數字陣列通常為已 “排序”

/**
 * @param {number[]} nums
 * @return {number[]}
 */

/**
 * Example 1
 * Input: nums = [1, 6, 3, 2, 7, 2]
 * Output: [1,7,10,12,19,21]
*/

var prefixSum = (nums) => {
  let prefix = [nums[0]]
  
  for(let i=1; i<nums.length; i++){
    prefix.push(prefix[i-1] + nums[i])
  }
  
  return prefix
}

// 或是更簡單的 js 
var prefixSum = (nums) => {
  let sum = 0
  let prefixSum = nums.map(num => sum += num)
  
  return prefix
}

Building a prefix sum is a form of pre-processing. Pre-processing is a useful strategy in a variety of problems where we store pre-computed data in a data structure before running the main logic of our algorithm. While it takes some time to pre-process, it’s an investment that will save us a huge amount of time during the main parts of the algorithm.

其他代表題

• 給一個數字陣列 nums = [10,4,-8,7]，split 成兩個陣列
  (有可能為 [10], [4, -8,7]10> 3 valid、[10,4], [-8,7]14> -1 valid、[10,4,-8], [7]6< 7 invalid 三種可能)，回傳第一個加總大於第二的的 valid splits，所以此範例答案為 2 。(2270. Number of Ways to Split Array)
• 找出最小的正整數 startValue，在依序跟數字陣列中每一個的相加結果都不能小於 1。( 1413. Minimum Value to Get Positive Step by Step Sum)
• 2090. K Radius Subarray Averages