763.划分字母区间

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
    // map记录之前的字符是否出现过
    let map = new Map()
    let res = [] // 记录片段
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i)
        // 贪心算法，不存在该字符，我自己就是一个片段！
        if (!map.has(char)) {
            res.push(char)
            map.set(char, true)
        } else { // 存在的话，看在哪一个片段里
            let index = res.findIndex(str => str.indexOf(char) > -1)
            // 合并片段
            let str = ''
            for (let j = index; j < res.length; j++) {
                str += res[j]
            }
            str = str + char // 加上当前字母
            res = res.slice(0, index)
            res.push(str)
        }
    }
    console.log(res)
    return res.map(str => str.length)
};

// 哈希+双指针
var partitionLabels = function (s) {
    let maxPos = {} // 记录每个字母出现的最远位置
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i)
        maxPos[char] = i
    }

    let res = []
    let sliceArr = []

    // 双指针切割片段
    let sliceStart = 0 // 待切割片段的起始位置
    let sliceEnd = 0 // 已扫描的字符的最远位置
    for (let i = 0; i < s.length; i++) {
        let charMaxPos = maxPos[s.charAt(i)]
        // 如果下一个字母的最远位置更远，则用最远的
        sliceEnd = Math.max(sliceEnd, charMaxPos)
        // 遍历到最远位置时就可以切割了
        if (i === sliceEnd) {
            res.push(sliceEnd - sliceStart + 1) // 题目结果只要输出长度
            sliceArr.push(s.slice(sliceStart, sliceEnd + 1)) // 片段
            sliceStart = i + 1
        }
    }
    console.log(sliceArr)
    return res
}

console.log(partitionLabels("ababcbacadefegdehijhklij"))