var binarySearch = function(nums, target) {
    // 一左一右两个指针相向而行
    var left = 0, right = nums.length - 1;
    while (left <= right) { // 闭区间
        var mid = Math.floor((right + left) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
};

var twoSum = function(numbers, target) {
	let left = 0
	let right = numbers.length - 1
	while(left < right) {
		const total = numbers[left] + numbers[right]
		if (total === target) {
			return [left + 1, right + 1]
		} else if (total < target) {
			left++
		} else if (total > target) {
			right--
		}
	}
	return []
};

var reverseString = function(s) {
	let left = 0
	let right = s.length - 1
	while(left < right) {
		swap(s, left, right)
		left++
		right--
	}
	return s
};

var isPalindrome = function(s) {
    // 一左一右两个指针相向而行
    let left = 0
    let right = s.length-1;
    while (left < right) {
        if (s.charAt(left) !== s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
};

function palindrome(s, l, r) {
	while (0 <= l && r < s.length && s[l] === s[r]) {
		l--
		r++
	}
	return s.substring(l + 1, r)
}
var longestPalindrome = function(s) {
	let ret = ''
	for (let i = 0; i < s.length; i++) {
		// 假设回文串长度为偶数，两个中心点分别传入 `l`、`r`。
		const even = palindrome(s, i, i + 1)
		// 假设回文串长度为奇数，一个中心点传入 `l`、`r`。
		const odd = palindrome(s, i, i)
		const max = even.length > odd.length? even: odd
		ret = ret.length > max.length? ret: max
	}
	return ret
};

this.preSum = [0]
// 添加了 BaseCase ，是为了动态规划表达式边界成立。
// 留意 i <= nums.length  
for (let i = 1; i <= nums.length; i++) {
	this.preSum[i] = this.preSum[i - 1] + nums[i - 1]
}

// 前缀和的定义是当前下标前所有值之和，不包含本身下标值
// 所以要取到 right 坐标本身的值，便需要 this.preSum[right + 1]
sumRange = function(left, right) {
	return this.preSum[right + 1] - this.preSum[left]
}

var NumMatrix = function(matrix) {
    const m = matrix.length
    const n = matrix[0].length
    // `preSum[i][j]` 的定义： 从原点 `[0, 0]` 到 `[i - 1, j - 1]` 所有值之和
    this.preSum = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0)) // base case

	// 计算每个矩阵 [0, 0, i, j] 的元素和
    for (let i = 1; i <= m; i++) { // 从 1 开始
        for (let j = 1; j <= n; j++) { // 从 1 开始
            this.preSum[i][j] = this.preSum[i - 1][j] + this.preSum[i][j - 1] + matrix[i - 1][j - 1] - this.preSum[i - 1][j - 1]
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
	// 所以我们要求区间原点至 `(x,y)` 之和，需要的是 `preSum[x+1][y+1]`
	// 区间内矩阵和通过分解矩阵，转换成都跟原点相关的矩阵。
    return this.preSum[row2 + 1][col2 + 1] - this.preSum[row1][col2 + 1] - this.preSum[row2 + 1][col1] + this.preSum[row1][col1] 
};

var diff = new Array(nums.length);
// 构造差分数组
diff[0] = nums[0];
for (var i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

var nums = new Array(diff.length);
// 根据差分数组构造结果数组
nums[0] = diff[0];
for (var i = 1; i < diff.length; i++) {
    nums[i] = nums[i - 1] + diff[i];
}

class Difference {
    constructor (nums) {
        this.diff = []
        const { length } = nums
        if(!length) return
        this.diff[0] = nums[0]
        for(let i = 1; i < length; i++) {
            this.diff[i] = nums[i] - nums[i - 1]
        }
    }
    increment(i, j, val) { /* 给闭区间 [i, j] 增加 val（可以是负数）*/
        this.diff[l] += val
        if (j + 1  > this.diff.length - 1) return // 如果超过范围，说明是对 nums[i] 及以后的整个数组都进行修改，不需要减了
        this.diff[j + 1] -= val
    }
    result() { /* 返回结果数组 */
        const nums = []
        const { length } = this.diff
        if (!length) return nums
        nums[0] = this.diff[0]

        for (let i = 1; i < length; i++) {
            nums[i] = nums[i - 1] + this.diff[i]
        }
        return nums
    }
}

const n = matrix.length
// 左上到右下对角线镜像对称
for (let i = 0; i < n; i++) {
	for (let j = i; j < n; j++) {
		swap(matrix, i, j, j, i)
	}
}

const n = matrix.length
// 右上到左下对角线镜像对称
for (let i = n; i >= 0; i--) {
	for (let j = n - 1 - i; j >= 0; j--) {
		swap(matrix, i, j, n - 1 - j, n - 1 - i)
	}
}

var spiralOrder = function(matrix) {
	    let left = 0, top = 0, right = matrix[0].length - 1, bottom = matrix.length - 1
	    let dire = 0
	    const ret = []
	    while (left <= right && top <= bottom) {
	        if (dire === 0) { // 向右
	            let j = left
	            while( j <= right) { // 不超过右边缘
	                ret.push(matrix[top][j])
	                j++
	            }
	            top++ // 上边界都处理过了，上边界往中间缩
	        } else if (dire === 1) {
	            let i = top
	            while ( i <= bottom) {
	                ret.push(matrix[i][right])
	                i++
	            }
	            right--
	        } else if (dire === 2) {
	            let j = right
	            while ( j >= left) {
	                ret.push(matrix[bottom][j])
	                j--
	            }
	            bottom--
	        } else if (dire === 3) {
	            let i = bottom
	            while ( i >= top) {
	                ret.push(matrix[i][left])
	                i--
	            }
	            left++
	        }
	        
	        dire = ++dire % 4
	    }
	    return ret
};

var slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据
    const map = new Map();
    
    let left = 0, right = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        map.set(c, (map.get(c) || 0) + 1);
         // 进行窗口内数据的一系列更新
        ...
        
        // 增大窗口，且是左闭右开
        right++; 
       

        console.log("window: [" + left + ", " + right + ")");
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) { // 如果是固定长窗口（固定长窗口例如判断 right - left === xx.size ），由于只移除1个字符,可以将 while 改成 if
            // d 是将移出窗口的字符
            let d = s[left];
            map.set(d, map.get(d) - 1);
            // 进行窗口内数据的一系列更新
            ...
            
            // 缩小窗口
            left++;
            
        }
    }
}

var minWindow = function(s, t) {
    let left = 0, right = 0, start = 0, length = Infinity
    const tMap = new Map()
    for (let i = 0; i < t.length; i++) {
        const str = t[i]
        tMap.set(str, (tMap.get(str) || 0) + 1)
    }

    const map = new Map()
    while(right < s.length) {
        const r = s[right]
        map.set(r, (map.get(r) || 0) + 1)
        right++

        while (left < right && isInWindow({map, tMap})) {
            const l = s[left]
            map.set(l, (map.get(l) || 0) - 1)
            
            const len = right - left
            left++

            if (length < len) {
                continue
            }

            length = len
            start = left - 1
        }
    }
    if (length === Infinity) return ''

    return s.substr(start, length)
};

// 当然可以优化掉该方法， 用一个计数器变量记录已满足字符串的数量
const isInWindow = ({map, tMap}) => {
    if (map.size < tMap.size) return false
    const entires = tMap.entries()
    for (let entry of entires) {
        const [s, tNum] = entry
        const num = map.get(s) || 0
        if (num < tNum) {
            return false
        }
    }
    return true
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    const needs = new Map()
    for (let s of s1) {
        needs.set(s, (needs.get(s) || 0) + 1)
    }
    let left = 0, right = 0, validate = 0
    const {length} = s2
    while (right < length) {
        const s = s2[right] // 因为左闭右开，此时的right是进入window的元素
        if (needs.has(s)) {
            needs.set(s, needs.get(s) - 1)
            if (needs.get(s) === 0) {
                validate++
            }
        }
        right++ // 左必右开

        while (validate === needs.size) { // 固定长，也可以用 if
            // 满足条件的子串，长度肯定跟s1一致
            const d = s2[left] // 即将离开window的元素
            /* 留意这里 */
            if (needs.has(d)) { // 反操作，留意是先判断计数器，再修改 needs
                if (needs.get(d) === 0) {
                    validate--
                }
                needs.set(d, needs.get(d) + 1)
            }
            if (right - left === s1.length) return true

            left++

        }
    }

    return false
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const map = new Map()
    let left = 0, right = 0, len = 0 
    const {length} = s
    while (right < length){
        const r = s[right]
        map.set(r, (map.get(r) || 0) + 1)
        right++

        while(map.get(r) > 1) { // 重复了，长度不在里面计算
            const l = s[left]
            map.set(l, map.get(l) - 1)
            
            left++
        }
        // 只有在跳出重复这个循环后，才能确保是不重复的,
        // 范围是[left, right)，计算长度: right - left 
        // 不用 + 1.  [left, right] 才需要 + 1. 可以参考 [0, 0) 和 [0, 0]
        len = Math.max(len, right - left)
    }
    if (!left) return length

    return len
};

let number = 8264
const appendVal = 3
const R = 10 // 进制
number = number * R + appendVal // 82643

let number = 8264
const removeVal = 3
const R = 10 // 进制
const L = 4 // number 位数
number = number - removeVal * R^(L - 1) // 264

var slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据
    const map = new Map();
    
    let left = 0, right = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
         // 进行窗口内数据的一系列更新
        ...
        
        // 增大窗口，且是左闭右开
        right++; 
       

        console.log("window: [" + left + ", " + right + ")");
        /********************/
        
        // 判断左侧窗口是否要收缩
        if (right - left === 10) { // 如果是固定长窗口（固定长窗口例如判断 right - left === xx.size ），由于只移除1个字符,可以将 while 改成 if
            // d 是将移出窗口的字符
            let d = s[left];
            // 进行窗口内数据的一系列更新
            ...
            
            // 缩小窗口
            left++;
        }
    }
}

const getNum = (s) => {
    switch(s) {
        case 'A':
            return 0
        case 'C':
            return 1
        case 'G':
            return 2
        case 'T':
            return 3
    }
}
/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    let left = 0, right = 0, nums = 0
    const map = new Map() // 计数器
    const set = new Set() // 重复的返回值
    const {length} = s
    const R = 4 // 进制
    const L = 10 // 长度
    const RL = Math.pow(R, L - 1) // 减去最高位所需倍数值 R^(L - 1)
    while (right < length) {
        const r = s[right]
        nums = nums * R + getNum(r)
        right++
        
        if (right - left === L) {
            const l = s[left]
            // 离开之前记录
            if (map.has(nums)) {
                set.add(s.slice(left, right))
            } else {
                map.set(nums, 1)
            }
            nums = nums - getNum(l) * RL
            left++
        }
    }
    
    return [...set.values()]
};

/*
	@params txt 文本串（原文本）
	@params pat 模式串（待匹配文本）
*/
function (txt, pat) {
	// 需要寻找的子串长度为模式串 pat 的长度  
	const L = pat.length();  
	// 仅处理 ASCII 码字符串，可以理解为 256 进制的数字  
	const R = 256;  
	// 存储 R^(L - 1) 的结果  
	const RL = Math.pow(R, L - 1);  
	// 维护滑动窗口中字符串的哈希值  
	let windowHash = 0;  
	// 计算模式串的哈希值  
	let patHash = 0;  
	for (let i = 0; i < pat.length(); i++) {  
	    patHash = R * patHash + pat.charCodeAt(i);  
	}  
	  
	// 滑动窗口代码框架  
	let left = 0, right = 0;  
	while (right < txt.length) {  
	    // 扩大窗口，移入字符（在最低位添加数字）  
	    windowHash = R * windowHash + txt.charCodeAt(right);  
	    right++;  
	  
	    // 当子串的长度达到要求  
	    if (right - left === L) {  
	        // 根据哈希值判断窗口中的子串是否匹配模式串 pat  
	        if (patHash === windowHash) {  
	            // 找到模式串  
	            console.log("找到模式串，起始索引为", left);  
	            return left;  
	        }  
	          
	        // 缩小窗口，移出字符（删除最高位数字）  
	        windowHash = windowHash - txt.charCodeAt(left) * RL;  
	        left++;  
	    }  
	}  
	// 没有找到模式串  
	return -1;
}

(X + Y) % Q === (X % Q + Y % Q) % Q
X % Q === (X + Q) % Q  

/*
	@params txt 文本串（原文本）
	@params pat 模式串（待匹配文本）
*/
function (txt, pat) {
	// 需要寻找的子串长度为模式串 pat 的长度  
	const L = pat.length();  
	// 仅处理 ASCII 码字符串，可以理解为 256 进制的数字  
	const R = 256;  
	// 取一个比较大的素数作为求模的除数  
    const Q = 1658598167;
    // 存储 R^(L - 1) 的结果  
	let RL = 1;  
    for (let i = 1; i <= L - 1; i++) {  
        // 计算过程中不断求模，避免溢出  
        RL = (RL * R) % Q;  
    }
	// 维护滑动窗口中字符串的哈希值  
	let windowHash = 0;  
	// 计算模式串的哈希值  
	let patHash = 0;  
	for (let i = 0; i < pat.length(); i++) {  
		// 计算过程中不断求模，避免溢出
	    patHash = (R * patHash + pat.charCodeAt(i)) % Q;  
	}  
	  
	// 滑动窗口代码框架  
	let left = 0, right = 0;  
	while (right < txt.length) {  
	    // 扩大窗口，移入字符（在最低位添加数字）  
	    windowHash = ((R * windowHash  % Q) + txt.charCodeAt(right)) % Q;  
	    right++;  
	  
	    // 当子串的长度达到要求  
	    if (right - left === L) {  
	        // 根据哈希值判断窗口中的子串是否匹配模式串 pat  
	        if (patHash === windowHash) {  
	            // 当前窗口中的子串哈希值等于模式串的哈希值  
                // 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突  
                if (pat === txt.slice(left, right)) {  
	                // 找到模式串  
		            console.log("找到模式串，起始索引为", left);  
                    return left;  
                }
	        }  
	          
	        // 缩小窗口，移出字符（删除最高位数字）  
	        windowHash = windowHash - txt.charCodeAt(left) * RL;
	        windowHash = ((windowHash - (txt.charCodeAt(left) * RL) % Q)   +   Q) % Q
	        // X % Q === (X + Q) % Q 
            // 因为 windowHash - (txt[left] * RL) % Q 可能是负数  
            // 所以额外再加一个 Q，保证 windowHash 不会是负数
	        left++;  
	    }  
	}  
	// 没有找到模式串  
	return -1;
}

function binarySearch(nums, target) {
    let left = 0, right = ...;

    while(...) {
        let mid = left + (right - left) / 2;
        if (nums[mid] === target) { // 编写这一块时，要理清楚下一个要搜索的区间。
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

	if (nums[mid] === target) {
		right = mid - 1 // [left, mid - 1] !! 重点，向左靠拢
		// 等同于 mid === right + 1 === left
	} 

	if (nums[mid] === target) {
		left = mid + 1 // [mid + 1, right]  !! 重点，向右靠拢
		// 等同于 mid === left - 1 === right
	} 

var search = function(nums, target) {
    let left = 0, right = nums.length - 1
    // 搜索区间 [left, right] 闭区间
    while (left <= right) { // [0, 0] 也算有值，不会遗漏不用打补丁
        const mid = left + Math.floor((right - left) / 2)
        if (nums[mid] === target) { // if 相等意味着找到
            return mid
        } else if (nums[mid] < target) { // 目标比中值大，在右区间，左边界缩小
            left = mid + 1 // [mid + 1, right] 由于是闭区间，mid 已经比较过了，需要 + 1
        } else if (nums[mid] > target) { // 目标比中值小，在左区间，右边界缩小
            right = mid - 1 // [left, mid - 1] 由于是闭区间，mid 已经比较过了，需要 - 1
        }
    }
    // while 结束代表整个区间都没找到，不满足返回 -1
    return -1
};

var searchRange = function(nums, target) {
    let left = 0, right = nums.length - 1
    // 搜索区间 [left, right] 闭区间
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (nums[mid] === target) {
            right = mid - 1 // [left, mid - 1] !! 重点，向左靠拢，继续缩小搜索区间
            // 等同于 mid === right + 1 === left
        } else if (nums[mid] < target) { // 目标比中值大，在右区间，左边界缩小
            left = mid + 1 // [mid + 1, right]
        } else if (nums[mid] > target) { // 目标比中值小，在左区间，右边界缩小
            right = mid - 1 // [left, mid - 1]
        } 
    }

    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] === target ? left : -1;
};

	if (nums[mid] === target) {
		right = mid - 1 // [left, mid - 1] !! 重点，向左靠拢，继续缩小搜索区间
		// 等同于 mid === right + 1 === left
	} 

var searchRange = function(nums, target) {
    let left = 0, right = nums.length - 1
    // 搜索区间 [left, right] 闭区间
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (nums[mid] === target) {
            left = mid + 1 // [mid + 1, right]  !! 重点，向右靠拢，继续缩小搜索区间
            // 等同于 mid === left - 1 === right
        } else if (nums[mid] < target) { // 目标比中值大，在右区间，左边界缩小
            left = mid + 1 // [mid + 1, right]
        } else if (nums[mid] > target) { // 目标比中值小，在左区间，右边界缩小
            right = mid - 1 // [left, mid - 1]
        } 
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (left - 1 < 0 || left - 1 >= nums.length) {
        return -1;
    }
    // 判断一下 nums[left - 1] 是不是 target
    return nums[left - 1] === target ? left - 1 : -1;
};

	if (nums[mid] === target) {
		left = mid + 1 // [mid + 1, right]  !! 重点，向右靠拢，继续缩小搜索区间
		// 等同于 mid === left - 1 === right
	} 

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)

        if (nums[mid] === target) {
            right = mid - 1 // [left, mid - 1]
        } else if (nums[mid] > target) {
            right = mid - 1 // [left, mid - 1]
        } else if (nums[mid] < target) {
            left = mid + 1 // [mid + 1, right]
        }
    }

    if (left < 0 || left >= nums.length || nums[left] !== target) return [-1, -1]

    const retLeft = left

    right = nums.length - 1
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (nums[mid] === target) {
            left = mid + 1 // [mid + 1, right]
        } else if (nums[mid] > target) {
            right = mid - 1 // [left, mid - 1]
        } else if (nums[mid] < target) {
            left = mid + 1 // [mid + 1, right]
        }
    }
    return [retLeft, right]

};

// 满足该模版
for (let i = 0; i < n; i++)  {
    if (fn(i)) {
        return answer;
    }
}

for (let i = 0; i < n; i++)  {
    if (nums[i] === target) {
        return answer;
    }
}

// 暴力
var minEatingSpeed = function(piles, h) {
	const max = getMax(piles)
	for (let speed = 1; i <= max; speed++) { // 连续的线性搜索
		if (canFinish(speed, piles, h)) {
			return speed
		}
	}
	return max
};

var minEatingSpeed = function(piles, h) {
	let left = 1, right = getMax(piles)
	while (left <= right) {
		const mid = left + Math.floor((right - left) / 2)
		// if (piles[mid] === h) {
		//	    right = mid - 1 // [left, mid - 1]
		//} else if (piles[mid] < h) {
		//  	left = mid + 1 // [mid + 1, right]
		//} else if (piles[mid] > h) {
		//  	right = mid - 1 // [left, mid - 1]
		//}
		if (canFinish(mid, piles, h)) { // 相等和速度快都需要搜索左区间，缩小右边以达到找左边界的目的
			right = mid - 1 // [left, mid - 1]
		} else {
			left = mid + 1 // [mid + 1, right]
		}
	}
	// 题意速度无限大，不会越界，不进行额外判断
	return left
};

/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function(weights, days) {
    // const max = getMax(weights)
    // for (let speed = 1; speed <= max; speed++) {
    //     if (canFinish(speed, weights, days)) {
    //         return speed
    //     }
    // }
    // return max
    
    let left = 1, right = getMax(weights)

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (canFinish(mid, weights, days)) {
            right = mid - 1 // [left, mid - 1]
        } else {
            left = mid + 1
        }
    }
    return left
};

const getMax = (weights) => {
    let total = 0
    for(let i = 0; i < weights.length; i++) {
        total += weights[i]
    }
    return total
}

const canFinish = (speed, weights, D) => {
    let i = 0
    for(let day = 1; day <= F; day++) {
        let remain = speed
        while (remain >= weights[i]) {
            remain -= weights[i]
            i++
            if (i === weights.length) return true
        }
    }
    return false
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function(nums, k) {
    const max = getMax(nums)
    // for (let maxVal = 0; maxVal <= max; maxVal++) { // 连续
    //     const dealK = getK(maxVal, nums) // 线性，nums 不变，maxVal 越大，分组 k 越小
    //     if (dealK === k) {
    //         return val
    //     }
    // }
    // 换个角度，只关心能不能满足条件，不关心 k 值
    // for (let maxVal = 0; maxVal <= max; maxVal++) { // 连续
    //     if (canFinish(maxVal, nums, k)) {  // 线性，nums 不变，maxVal 越大，分组 k 越小
    //         return val
    //     }
    // }
    
    // 当然，要优化可以优化 left，他是数组里最小的那个值。
    let left = 0, right = max
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (canFinish(mid, nums, k)) { // 线性，nums 不变，maxVal 越大，分组 k 越小
            // 横坐标是和最大值，从小到大，我们要找最大值最小，所以是找左边界
            // 满足时，下一个搜索区间是左区间，继续缩小搜索范围 [left, mid - 1]
            right = mid -1
        } else {
            left = mid + 1
        }
    }
    return left
};

const getMax= (nums) =>{
    return nums.reduce((prev, now) => prev + now, 0) // 一个数组和最大，虽然会扩大搜索范围，但对于二分搜索没关系
}

const canFinish = (maxVal, nums, K) => {
    let i = 0
    for (let k = 1; k <= K; k++) {
        let remain = maxVal
        while(remain >= nums[i]) {
            remain -= nums[i]
            i++
            if (i === nums.length) {
                return true
            }
        }
    }
    return false
}