因为这一周有2Sum的题目，所以也重新做了一下3Sum，sum类的题目再做的时候再怎么样也能想起大概该怎么做，只是总是有些细节的地方会忘记，比如3sum要求去重，所以sort之后遍历的时候，如果已经以这个数为目标找过有无匹配的数了，就应该跳过这些已经匹配过的数，所以三个数都要检查有没有重叠。
刚刚又做了4sum，发现sum题的规律就是：如果是2sum，最优解时间复杂度是o(n), 3sum最优解时间复杂度是o(n^2), 4sum最优解时间复杂度是o(n^3).
突然发现记一道题的解法可以从记时间复杂度记起，因为时间复杂度比较容易记，然后当碰到类似题的时候，只要自己的解法跟记住的时间复杂度是一样的，应该就没什么问题了。想起面试的时候面试官基本都会问有没有更优的解法。
还有就是sum的题目经常会用到hash表，因为sum题本质上就是找match。
Read full article from Sum题总结，大家一起来总结哇 - AcWing
No comments:
Post a Comment