Skip to content

完成算法题中获得的经验 2

其实这里可以继续写在 experience1 里面的,但为了实现时间顺序编写,还是打算新建一个文件。

经验

是否加等号,是否要 +1,两条语句哪个前哪个后

做算法题时,当发现结果不通过时,或者下标越界时,或者发现结果和答案刚好相差 1 时,我们往往会思考:

  • 这里的 while 循环是不是应该加上等号,或者不加上等号。
  • 这里计算长度时是不是应该 +1,或者 -1

这些思考本身没问题,但要具体情况具体分析。详见 leeCode 209 题:

  • 当两个数值的含义是双下标时,计算长度的时候就肯定要 +1,如果此时错误,那应该思考其他地方的逻辑,而不应该直接修改这里的计算长度
  • 同理,while 循环判断时,如果是下标与长度的判断,那么 while 循环肯定不可以加等号,这样这肯定会越界!
  • 同理,如果不加等号时还越界,那么你就应该思考 while 循环内部是否有错误,而不是想着修改 while 循环的判断语句为下标 +1,比如 index + 1 < len。
  • while 循环内部,当需要对下标 ++ 时,同样应该思考初识状态和终止状态,根据情况的不同,将会决定这条语句的位置不同,如果下标是从 -1 开始,那么你就应该先 ++,然后再获取下标所在值。如果下标是从 0 开始,那么你就应该先获取值,然后再 ++。

总之,当出现错误时,确实应该思考每个地方是不是应该加等号,或者 +1,或者 -1。但一定不要想着直接先改掉,然后提交看看,错了再从重新改。虽然这样确实可能可以直接 AC 了,但大多数情况是没有这么好运气的。所以当你改了后又错误时,你可能就会乱了思绪。

故,当你在考虑是否应该加等号、+1、-1 时,你应该思考当前这里的值是什么情况:

  • 它代表是的下标值,那么计算长度时它就应该 +1
  • 但这也不是绝对的,因为 +1 计算出来的长度,可能和你想要的长度不一致。

总之,直接看下面的案例代码更好理解!

js
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    const len = nums.length
    if (len < 1) {
        return nums[0] && nums[0] >= target ? 1 : 0
    }

    let leftIndex = 0
    // 这里设置成 -1 是不合适的。但在不合适的情况下同样能 AC,也是一种锻炼!
    let rightIndex = -1
    let curSum = 0
    let minLen = Infinity

    // 2. 因为 rightIndex 是作为下标,所以肯定不可以相等!
    // 这里也同理,答案不对时,不要想着改成 <= 。而是应该重新思考
    // 逻辑是否正确,或者哪里的条件没考虑到。
    while (rightIndex < len) {
        if (curSum >= target) {
            // 1. 既然这里是根据两个下标计算长度,那么肯定就是要 +1 的
            // 如果 +1 后答案不对,那应该重新检查逻辑,而不是取消
            // 这里的 +1
            minLen = Math.min(minLen, rightIndex - leftIndex + 1)

            // 4. 因为 leftIndex 是下标,而且是从 0 开始的,
            // 所以这里应该先减去下标对应值,然后再让左边界移动
            curSum -= nums[leftIndex]
            leftIndex++
        } else {
            rightIndex++
            // 3. 于是我们发现是这里错误了。
            // 因为 ++ 在前面,会导致这里越界,所以我们这里需要判断一下
            if (rightIndex < len) {
                curSum += nums[rightIndex]
            }
        }
    }


    // 这一段代码是第一次 AC 后残留下来的,当时没注意
    // 当重新理清一遍思路后回看这段代码,就会发现这段代码是不合适的。
    // 首先,这里的 while 一定是需要等号的,因为就是 curSum 是在 minLen 后面
    // 更新的,所以当 curSum 更新后,我们还需要再次更新 minLen 的值
    // 那么这里就一定是需要添加等号的!
    // 然后,当我发现不添加等号时也能成功 AC,那是不是说明刚刚的推理是错误的呢?
    // 不不不,这切切说明这一段代码无用的!因为 curSum 和 target 相等的情况
    // 已经被前面处理好了,所以这里的处理完全是多余的!将其注释掉
    // 后就会发现同样可以 AC!
    // while (curSum > target) {
    //     minLen = Math.min(minLen, rightIndex - leftIndex + 1)
    //     curSum -= nums[leftIndex]
    //     leftIndex++
    // }

    return minLen === Infinity ? 0 : minLen
}
js
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    const len = nums.length
    if (len < 1) {
        return nums[0] && nums[0] >= target ? 1 : 0
    }

    let leftIndex = 0,
    rightIndex = 0 // 1. 我们这里改成了从 0 开始
    let curSum = 0
    let minLen = Infinity
    while (rightIndex < len) {
        if (curSum >= target) {
            // 3. 同时要注意的是,此时的 rightIndex 是比 curSum 的
            // 右边界提前一格子的,因为 rightIndex++ 是在我们计算 minLen
            // 之后才变化的,所以这里不需要加 1
            minLen = Math.min(minLen, rightIndex - leftIndex)

            curSum -= nums[leftIndex]
            leftIndex++
        } else {
            // 2. 那么这里就可以先计算下标所在值
            // 然后再对下标 ++
            curSum += nums[rightIndex]
            rightIndex++
        }
    }

    // 5. 因为 while 循环中的 curSum 是在计算 minLen 后面更新的
    // 所以需要添加等号,这样当 curSum 更新后,才可以获得
    // 新的 minLen 值
    while (curSum >= target) {
        // 4. 同理,当前面的循环出来后,这里的 rightIndex 其实等于 len
        // 的大小,所以不需要 +1
        minLen = Math.min(minLen, rightIndex - leftIndex)

        curSum -= nums[leftIndex]
        leftIndex++
    }

    return minLen === Infinity ? 0 : minLen
}