算法 | 子序列问题一网打尽

此文章中的题目都是Leetcode上 子序列/子串 问题相关的汇总, 点击相应标题可以跳转到该问题。
持续更新中 ...

Leetcode 53. 最大子序和

简单题 动态规划
此题存在明显的递推关系，因此可以用通用的动态规划法来做。
时间复杂度: O(n) 【具体来说是2n，dp过程是n，求数组的max也是n】
空间复杂度: O(n) 【dp辅助数组是n】

var maxSubArray = function(nums) {
    /**
     * dp[i]代表第i个数结尾的子数组的最大和
     * 因此当dp[i-1] < 0时，dp[i]最大值是nums[i]
     * dp[i-1] > 0时，dp[i]最大值是nums[i]+dp[i-1]
     * 返回的总最大值是max(dp)
     */
    const len = nums.length
    if(len === 0) {
        return
    }
    if(len === 1) {
        return nums[0]
    }
    const dp = new Array(len)
    dp[0] = nums[0]
    for(let i=1;i<len;i++) {
        dp[i] = dp[i-1]<0 ? nums[i] : nums[i] + dp[i-1]
    }
    return Math.max.apply(null, dp)
};

进一步发现辅助数组dp可以去除，因为dp[i]只依赖dp[i-1]的结果，我们只需要缓存上一个结果就行了，求max也可以在迭代过程中求。
时间复杂度: O(n)
空间复杂度: O(1)

var maxSubArray = function(nums) {
    const len = nums.length
    if(len === 0) {
        return
    }
    if(len === 1) {
        return nums[0]
    }
    let num = 0, max = -Infinity
    for(let i=0;i<len;i++) {
        num = num < 0 ? nums[i] : nums[i] + num
        max = num > max ? num : max
    }
    return max
};

Leetcode 647. 回文子串

中等题 动态规划
主要点在回文的状态转移方程：dp[i][j] = (s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])
迭代时候需要注意，dp的某一项依赖它左下角的值(i+1,j-1)，并且dp是一个上三角形，对角线的值可以独立求出，因此遍历应该从对角线出发，从下到上，由左及右。

var countSubstrings = function(s) {
    /**
     * dp[i][j] 代表i到j是否为回文子串
     * dp[i][j] 是回文子串 -> 一个字母时成立，两个字母时两个字母相同成立，三个以上字母时首尾字母相同，并且中间也是回文串<->dp[i+1][j-1]=true
     * dp[i][j] = (s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])
     */
    const len = s.length
    let res = 0
    const dp = Array(len).fill(0).map(item => Array(len))
    for(let j=0;j<len;j++) {
        for(let i=j;i>=0;i--) {
            if((s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])) {
                dp[i][j] = true
                res++
            }
        }
    }
    return res
};

Leetcode 3. 无重复字符最长子串

中等题 动态规划 滑动窗口
假设使用暴力法：n长度的数组，子数组数量为n(n-1)/2，判断一个子数组是否有重复字符则需要O(n)的时间复杂度，因此总体复杂度为O(n^3)。

用动态规划来优化的话，设dp[i]为以i为结尾的无重复最长字符子串的长度。
则如果str[i]没有出现过的话，dp[i] = dp[i-1] + 1;
str[i]出现过，设与str[i]最近的同一个字符为str[j]，
i - j <= dp[i-1]，则j出现在i-1的无重复最长字符子串中，且(j,i]中没有重复字符，所以以i为结尾的无重复字符子串的长度是 i - j，dp[i] = i - j。
i - j > dp[i-1]，那么显而易见dp[i] = dp[i-1] + 1;

const lengthOfLongestSubstring = function(s) {
    const len = s.length
    if (!len) {
        return 0
    }
    const dist = {}
    const dp = new Array(len)
    dp[0] = 1
    dist[s[0]] = 0
    for(let i=1;i<len;i++) {
        if(!(s[i] in dist)) {
            dp[i] = dp[i-1]+1
            dist[s[i]] = i
        } else {
            distance = i - dist[s[i]]
            dist[s[i]] = i
            if (distance <= dp[i-1]) {
                dp[i] = distance
            } else {
                dp[i] = dp[i-1]+1
            }
        }
    }
    return Math.max.apply(null, dp)
};

题解还提及到滑动窗口的解法，明天再看看。

Leetcode 128. 最长连续序列

困难题 哈希表
这道题其实用js来实现并不算难，题目要求复杂度O(n)，其实只要借助自带的Set就能方便的实现这一点。

var longestConsecutive = function(nums) {
    let longgest = 0
    let tmp = 0
    const hashSet = new Set(nums)
    for(let num of nums) {
        if(!hashSet.has(num-1)) {
            tmp = 0
            for(let i = num; hashSet.has(i); i++) {
                tmp++
            }
            longgest = Math.max(longgest, tmp)
        }
    }
    return longgest
};

Leetcode 76. 最小覆盖子串

困难题 滑动窗口法

滑动窗口法在子串问题中有很多采用此方法。

var minWindow = function(s, t) {
    /**
     * 滑动窗口法
     */
    let start, minLen = Infinity // 最小串的起始和长度
    const needs = {} // t字符串的哈希表
    const win = {} // 目前窗口的哈希表
    for(let c of t) {
        needs[c] = needs[c]?needs[c]+1:1
    }

    let match = 0
    let right = 0, left = 0
    // 执行right膨胀计划
    while(right < s.length) {
        // 如果right字符在need哈希表中存在的话，win哈希表计数加一，如果win哈希表值和need哈希表值相等(不能是大于等于,注意)，则匹配值match加一
        if(s[right] in needs) {
            win[s[right]] = win[s[right]] ? win[s[right]]+1 : 1
            if(win[s[right]] === needs[s[right]]) {
                match++
            }
        }
        // 如果匹配率match和need长度一致，窗口中包含了s所有字母。
        // 执行left收缩计划
        while(match === Object.keys(needs).length) {
            // 先检查是否可以更新最小串
            if(right - left + 1 < minLen) {
                minLen = right - left + 1
                start = left
            }
            if(s[left] in needs) {
                win[s[left]] = win[s[left]] ? win[s[left]]-1 : 0
                if(win[s[left]] < needs[s[left]]) {
                    match--
                }
            }
            left++
        }
        right++
    }
    return minLen===Infinity?'':s.substr(start,minLen)
};