尺取,差分,前缀和经验分享

一、区间和的简单导图:


区间和的思路大概就是既然题目数据开的大,操作时又有重复且相等的操作,那我不如直接全算一遍。
暴力的写法二维能达到O(nmq),但前缀和是O(nm+q)。(二维)
二、差分的简单思维导图:

看题意就已经能猜个大概了,就跟前缀和反一反嘛。

三、双指针:

双指针其实就是一种优化时间复杂度的算法。
就是搞两个变量,这两个变量本来应该是两重循环的,但是你发现他们有一些内在关系,其中一个变化了另一个也会有变化,而总的变化次数大概是O(n)的。

四、尺取法
就是,像尺子一样取一段取一段取一段。
尺取法一般都是在数组里头记录一对下标,就是要选取的区间的左右端点,然后根据实际情况不断地挪动区间的左右端点从而得出答案。
尺取法比直接枚举区间效率高很多很多,特别是数据量很大的时候,所以说尺取法是一种很好使方法,一般用于求出有一定限制的区间个数或着是最短的区间等等。

差不多没了


好吧,是我前面懂了,结不出来;后面不懂,结不动了……

1 个赞