周赛352 | 顾澜的技术小站

2760. 最长奇偶子数组

解题思路：

根据题意把数组分为若干子串，计算最长子串返回即可

func longestAlternatingSubarray(nums []int, threshold int) int {
    right, n := 0, len(nums)
    var res int
    for right < n {
        if nums[right]%2 > 0 || nums[right] > threshold {
            right++
        } else {
            left := right
            right++
            for ; right < n && nums[right] <= threshold && nums[right]%2 != nums[right-1]%2; right++ {
            }
            res = max(res, right-left)
        }
    }
    return res
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

2761. 和等于目标值的质数对

解题思路：

先预处理 $n$ 内的所有质数，可以使用埃氏筛和线性筛两种方式

然后就是暴力枚举质数 $x$ 和 $y = n-x$ ，如果 $x \le y$ 且 $y$ 是质数，那么就把 $[x,y]$ 加入答案

代码实现时，有一些优化之处：如果 nnn 是奇数，由于只有奇数+偶数=奇数，而偶数中只有 222 是质数，所以如果 nnn 是奇数时，至多只有一个质数对 (2,n−2)(2,n-2)(2,n−2)。

func findPrimePairs(n int) [][]int {
    var primes []int
    isP := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isP[i] = true
    }
    for i := 2; i <= n; i++ {
        if isP[i] {
            primes = append(primes, i)
            for j := i * i; j <= n; j += i {
                isP[j] = false
            }
        }
    }
    
    //  代码实现时，发现一处可以优化的地方，如果n为奇数，且奇数+偶数=奇数，而质数中会有2为偶数，所以此时只存在一个质数对[2,n-2]
    if n%2 > 0 {
        if n > 4 && isP[n-2] {
            return [][]int{{2, n - 2}}
        }
    }
    var res [][]int
    for _, x := range primes {
        y := n - x
        if x <= y && isP[y] {
            res = append(res, []int{x, y})
        }
    }
    return res
}

代码实现时，发现一处可以优化的地方，如果 $n$ 为奇数，且 $奇数+偶数=奇数$ ，而质数中会有 $2$ 为偶数，所以此时只存在一个质数对 $[2,n-2]$

2762. 不间断子数组

解题思路：

使用「滑动窗口」的方式遍历数组，维护窗口内的数字。

根据题意，窗口内数字绝对差最多为 $2$ ，使用哈希表来维护即可。如果窗口内最大值与最小值的差大于 $2$ ，就不断移动左端点 $left$ ，减少窗口内的数字。

一个滑动窗口内存在的子数组：

$[left,right],[left+1,right],...,[right,right]$

整个窗口中一共有 $right-left+1$ 个子数组是合法的，加入答案即可。

func continuousSubarrays(nums []int) int64 {
    cnt := map[int]int{}
    left := 0
    var res int64
    for right, n := range nums {
        cnt[n]++
        for {
            mixN, maxN := n,n
            for c := range cnt {
                mixN = min(c, mixN)
                maxN = max(c, maxN)
            }
            if maxN-mixN <= 2 {
                break
            }
            y := nums[left]
            cnt[y]--
            if cnt[y] == 0 {
                delete(cnt, y)
            }
            left ++
        }
        res += int64(right-left+1)
    }
    return res
}

func max(a, b int) int { if b > a { return b }; return a }
func min(a, b int) int { if b < a { return b }; return a }

2763. 所有子数组中不平衡数字之和

枚举：

因为 $n$ 最大为 $1000$ ，所以我们可以从左到右枚举子数组的左端点 $i$ ，然后从 $i+1$ 开始向右枚举子数组右端点 $j$ ，一边维护 不平衡数字 $cnt$ 。

枚举右端点时会出现两种情况：

如果 $num = nums[j]$ 之前出现过，那么子数组排序后必然会和另一个 $num$ 相邻，此时 $cnt$ 不变
如果 $num = nums[j]$ $n u m = n u m s [j]$ 之前没出现过，那么看 $num-1$ $n u m - 1$ 和 $num+1$ $n u m + 1$ 出现过：
- 都没有则 $cnt$ 加一
- 只有一个， $cnt$ 不变
- 两个都有， $cnt$ 减一

遍历过程中，累加 $cnt$ ，即为答案。

func sumImbalanceNumbers(nums []int) int {
    n := len(nums)
    res := 0
    vis := make([]int, n+2)
    for i, _ := range vis {
        vis[i] = -1
    }
    for i, num := range nums {
        vis[num] = i
        cnt := 0
        for j := i + 1; j < n; j++ {
            x := nums[j]
            if vis[x] != i {
                cnt++
                if vis[x-1] == i {
                    cnt--
                }
                if vis[x+1] == i {
                    cnt--
                }
                vis[x] = i
            }
            res += cnt
        }
    }
    return res
}

贡献法：

对于一个包含 $x = nums[i]$ 的子数组来说，我们分左右两侧讨论

$x$ 的右侧没有 $x$ ，且不包含 $x-1$ ，最右侧下标为 $r_i$
$x$ 的左侧可以有 $x$ ，且不包含 $x-1$ ，最左侧下标为 $l_i$

此时 $x$ 产生子数组个数为 $(i-l_i)*(r_i-i)$ 。

我们在讨论 $x$ 时，求得的子数组部分，在 $x+1$ 讨论时肯定是不符合要求的，所以当 $x$ 为 $nums[l_i,r_i]$ 中最小值时不能作为贡献，而且是不合法的，相当于没个子数组都多算了一个不合法的贡献，最后需要减去

func sumImbalanceNumbers(nums []int) (res int) {
    n := len(nums)
    right := make([]int, n)
    idx := make([]int, n+1)
    for i := range idx {
        idx[i] = n
    }
    for i := n - 1; i >= 0; i-- {
        x := nums[i]
        right[i] = min(idx[x], idx[x-1]) // nums[i] 右侧的 x 和 x-1 的最近下标（不存在时为 n）
        idx[x] = i
    }
    
    for i := range idx {
        idx[i] = -1
    }
    for i, x := range nums {
        res += (i - idx[x-1]) * (right[i] - i) // 子数组左端点个数 * 子数组右端点个数
        idx[x] = i
    }
    
    return res - n*(n+1)/2 // 减去不合法子数组之和
}