[演算法筆記] Two Pointer & Prefix sum
演算法系列文
[Array & String]
- Sliding window
- Two Pointer & Prefix sum
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 — 1
at 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=0
Move along both inputs simultaneously until all elements have been checked.
Key Point
- 適用情境: 兩個 array 或 兩個字串
- 時間複雜度: Big O(n+m) if
n = arr1.length
andm = 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