题解 | #牛牛的彩虹数组#

牛牛的彩虹数组

https://www.nowcoder.com/practice/857d6f49e3ee4e568cc243cbf9956efd

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findRainbow(vector<int>& nums) {
        // write code here
        // 如果是第一次遇到子序列和子数组的概念，可能会搞不清楚两者区别。
        // 原始数组：[1,2,3,4,5]
        // 子序列：从原始数组里选一些元素，元素可以不连续，但一定要保持原始的相对顺序
        // 子序列举例：[]，[1,3,5]，[2,4]，[1,2,5]
        // 子数组：从原始数组里连续选取一整段出来。
        // 子数组举例：[]，[1,2,3]，[2,3]，[1,2,3,4,5]
        // 可以看出来，子数组一定是子序列，反过来不一定对。
        //
        // 这个问题要利用同余定理
        // 简单介绍一下同余定理的应用，如果两个数除以同一个数得到的余数相同，
        // 这两个数相减的结果正好是前面相同除数的倍数。
        // 举例：9 / 7 = 1 ... 2，16 / 7 = 2 ... 2，16 - 9 = 7 = 7 * 1
        //
        // 这道题还是前缀和思想，对每个前缀和取模 7 之后的结果，记录每种结果第一次出现的位置。
        // 如果在某个位置上再次出现相同的模 7 结果，两个位置之间的子数组的和是 7 的倍数。
        // 如果某个前缀和的结果直接模 7 就是 0，那也不用再找了，已经找到了。
        // 如果某个元素本身就是 7 的倍数，那也不用再找了，长度为 1 的子数组（也是子序列）找到了。
        unordered_map<int, int> modMap;
        modMap[0] = -1;
        int prefixSum = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 7 == 0) {
                // cout << "nums[i] % 7 == 0" << endl;
                return 1;
            }

            prefixSum += nums[i];
            int mod = prefixSum % 7;
            // cout << "mod = " << mod << endl;
            
            if (modMap.find(mod) != modMap.end()) {
                // cout << "modMap.find(mod) != modMap.end()" << endl;
                return 1;
            }
            modMap[mod] = i;
        }

        // 什么条件都不满足，找不到，直接返回 0
        // 多提一嘴，我这种思路一直在找子数组，而子数组是子序列的特例，判断其实是不完整的
        // 如果要找不连续的子序列，上面的代码就抓瞎了。
        // 举个例子，输入是 [1,2,3,12,5]，如果按照题意是能找到 [2,12] 或者 [2,5] 这样的子序列的，
        // 但是上面的代码只能找子数组找不到子序列。
        return 0;
    }
};

上面的代码目前来说可以 AC，但是我感觉这里有点问题。

把打印临时结果都开开，是这样的