在198号问题中，for( int j=i; j<i+2 && j<n; j++)，这样就是O(n)的时间复杂度
来源：9-4 状态的定义和状态转移 House Robber
慕斯卡7339178
2020-11-20
可以这样优化，在计算第i个时，只需计算 要么取i要么不取i
您好，我想问下，我在确定这个 j++ 终止条件时候，j 是应该 <=i+2 还是 <i+2 ，总是要想很久，干想还想不出，需要给一个简单的比如长度n为5的一个例子，然后在纸上一步一步debugger。所以处理边界问题这类问题有没有什么训练的方法，让我不需要debugger就能明了。
我考虑的10来分钟，想到 是不是只要判断 在 j>=i+2 中不可能出现比 j=i 与 j=i+1 两种情况下还要大的值 ，所以无需计算 >=i+2 的情况 。
举反例是不是一种解决方法，还有什么方法呢
1回答
-
liuyubobobo
2020-11-21
用一个特殊用例来确定边界是非常常用，也是非常简洁的方式。这个方式没有什么不好的。时间长了，熟练了，就快了。
另外一个判断边界的方式就是明确清楚每一个变量的语义，然后根据变量的语义判断边界。这一点我在课程的 3-2 我用二分搜索法为例进行了介绍。
最后，在一些代码中，可以靠变量本身的“界”来确定。比如对于你的代码，如果 j 可以等于 i - 2，而 i 是从 n - 2 开始的，那么就意味着 j 可以等于 n，而下面对 nums[j] 的调用，如果 j 等于 n，旧数组越界了。
对于这一点，在你的代码中，你使用了一个 && j < n 规避了。但其实只要 j < i + 2，不用这个 && j < n 也没有问题。因为 j < i + 2，j 就一定 < n。但 j <= i + 2 则不保证这一点。
继续加油！：）
20
相似问题