leetcode 404 周赛找出有效子序列的最大长度 II「暴力」「动态规划」

3202. 找出有效子序列的最大长度 II

题目描述

给你一个整数数组 $n u m s$ 和一个正整数 $k$

$n u m s$ 的一个子序列 $s u b$ 的长度为 $x$ ，如果其满足以下条件，则称其为 有效子序列

$\% k == (sub[1] + sub[2]) \% k == ... == (sub[x - 2] + sub[x - 1]) \% k$

返回 $n u m s$ 的 最长有效子序列 的长度。

数据范围：

2 <= nums.length <= $10^3$
1 <= nums[i] <= $10^7$
1 <= k <= $10^3$

思路1：巧妙的“暴力”

这是我赛时的思路，一种比较巧妙的暴力，就是写起来有点费力

观察数据范围，n和k都是1000，显然正确答案的复杂度应该类似于O(n * k)，即1000 * 1000

由于题目的要求：相邻两个数求和对k去模后结果一样，所以我们可以考虑先枚举余数p

此时问题变成了，给定余数 $p$ 和数组 $n u m s$ ，求一个最长的子序列，满足相邻两项求和模 $k$ 等于 $p$ ，此时考虑枚举子序列的起点 $n u m s [i]$ ，由于余数 $p$ 是固定的，我们可以求出子序列的下一个数为 $(p - n u m s [i] + k)$ ，这样我们就不难发现，只要确定了第一个数字和余数p，这条最长的子序列就能确定下来

比如，1 1 2 0 1 1 2 1 2 1 2，假设k是4，当前枚举的余数p是3，只要确定了起点1，那其对应的最长的子序列就是1 2 1 2 1 2 1 2，此时我们需要一种方法可以快速获得下标大于 $i$ 的某个特定数的下标，从而实现下标的跳转

虽然 $n u m s [i] <= 1 e 7$ ，但是对k取模后，数据范围就变成0到k-1了，所以我们可以考虑开一个vector数组v，对于nums[i]我们在vector数组里存下他的下标，即 $v[nums[i]\%k].push\_back(i)$ ，然后再搞一个id数组，id[x]代表vector[x]现在用到的下标，这样可以避免重复遍历

我们可以再搞一个vis数组标记一下，因为我们通过跳转得到的一个子序列，从中间的任意一个元素开始跳都不会比起点开始更长，所以标记一下以后这些点就不会再重复计算了，当然还有一种情况是，存在一些中间多余的数字，比如1 1 2 1 1 2 1 2 1 2，最长的序列是1(1) 2 1 (1) 2 1 2 1 2，中间的两个1在跳转的过程中不会被遍历到，vis也不会标记它，此时id[1]和id[2]的位置也已经到了最后面，理论上从它开始跳转根本不会按正常的跳转方式得到一个完整的子序列，这种情况下是否会影响答案呢？

答案是不会影响的，看刚刚的例子，被省略的两个1，前面已经存在过1了，以1开头最长的子序列长度已经确定了，其他的1再开始也不会比他更长，所以是不会影响答案

不难发现，第二层看上去虽然是一层for一层while，但其实每个点只访问了一次，所以是O(n)的，所以这个代码的复杂度是O(n * k)

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int tr[1005];
        int n = nums.size();
        vector<int>v[1005];
        for(int i = 1; i <= n; ++i){
            tr[i] = nums[i - 1];
            tr[i] %= k;
            v[tr[i]].push_back(i);
        }
        int ans = 0;
        for(int p = 0; p < k; ++p){//枚举余数
            bool vis[1005];
            memset(vis, 0, sizeof(vis));
            int id[1005];
            memset(id, 0, sizeof(id));
            for(int i = 1; i <= n; ++i){//枚举起点
                if(vis[i])continue;
                vis[i] = 1;
                int num = 1;
                int a = tr[i];
                int pos = i;
                while(1){
                    int b = (p - a + k) % k;
                    while(id[b] < v[b].size()){
                        if(v[b][id[b]] <= pos){
                            ++id[b];
                        }
                        else break;
                    }
                    if(id[b] < v[b].size() && v[b][id[b]] > pos){
                        pos = v[b][id[b]];
                        vis[pos] = 1;
                        ++num;
                        a = b;
                    }
                    else break;
                }
                ans = max(ans, num);
            }
        }
        return ans;
    }
};

思路2：dp

确定了余数p和第一个数，这个序列就确定了，会是两个数字循环

所以我们可以考虑用 $d p [n u m [i]]$ 表示以 $n u m [i]$ 结尾的子序列的最长长度

转移方程很简单， $d p [n u m s [i]] = d p [(p - n u m s [i] + k)$

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;
        for(int p = 0; p < k; ++p){
            vector<int>dp(k, 0);
            for(int i = 0; i < nums.size(); ++i){
                nums[i] %= k;
                dp[nums[i]] = dp[(p - nums[i] + k) % k] + 1;
                ans = max(ans, dp[nums[i]]);
            }
        }
        return ans;
    }
};