完成算法题中获得的经验 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
}