最長(zhǎng)奇偶子數(shù)組

【雙指針】l指針記錄數(shù)組開(kāi)頭，r指針記錄指針結(jié)尾。更新的時(shí)候碰到第一個(gè)不滿足的元素，更新長(zhǎng)度并重置子數(shù)組。

和等于目標(biāo)值的質(zhì)數(shù)對(duì)

【預(yù)處理 + 枚舉】預(yù)處理10^6內(nèi)所有質(zhì)數(shù)，然后暴力枚舉質(zhì)數(shù)x和y=n-x，如果x≤y且y是質(zhì)數(shù)，就把[x,y]加入答案。加個(gè)優(yōu)化：如果n是奇數(shù)，因?yàn)槠鏀?shù) = 奇數(shù)+偶數(shù)，而偶數(shù)中只有2是質(zhì)數(shù)，如果n是奇數(shù)時(shí)，至多只有一個(gè)質(zhì)數(shù)對(duì)(2, n - 2)。

不間斷子數(shù)組

【滑動(dòng)窗口】遍歷數(shù)組的同時(shí)，維護(hù)窗口內(nèi)的數(shù)字，用哈希表或平衡樹(shù)維護(hù)。如果窗口內(nèi)最大值與最小值的差大于2，就不斷移動(dòng)左端點(diǎn)l，減少窗口內(nèi)的數(shù)字。

所有子數(shù)組中不平衡數(shù)字之和

【O(n^2) 枚舉】題中n至多為1000，可以從左到右枚舉子數(shù)組左端點(diǎn)i，然后從i+1開(kāi)始向右枚舉子數(shù)組右端點(diǎn)j，一邊枚舉j，一邊維護(hù)不平衡度cnt：如果x=nums[j]之前出現(xiàn)過(guò)，那么排完序后與另一個(gè)x相鄰，cnt不變；如果x之前沒(méi)出現(xiàn)過(guò)，那么看x+1和x-1出現(xiàn)過(guò)沒(méi)，都出現(xiàn)了cnt--，都沒(méi)出現(xiàn)cnt++，只出現(xiàn)過(guò)1個(gè)cnt不變。代碼中vis數(shù)據(jù)可以用時(shí)間戳標(biāo)記。

【O(n) 貢獻(xiàn)法】?jī)纱伪闅v，第一次遍歷用r數(shù)組記錄每個(gè)數(shù)字右側(cè)最近的x和x-1的下標(biāo)。第二次遍歷中，對(duì)于每個(gè)位置i和其對(duì)應(yīng)的數(shù)字nums[i]和r[i]，計(jì)算貢獻(xiàn)為(i - idx[x - 1]) * (r - i)，但由于上述計(jì)算會(huì)多算每個(gè)子數(shù)組的最小值產(chǎn)生的貢獻(xiàn)，所以需要減去n * (n + 1) // 2。