力扣每日打卡挑战 3184. 构成整天的下标对数目 I

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推

这个题目特别简单，因为数据范围只有100，直接两重循环，完全不存在超时的问题，一个枚举i，一个枚举j，然后判断是否和为24的倍数就可以了。不过因为hours数组的最大值是1e9，还有求和，所以为了保险起见避免爆int，我用了long long

时间复杂度O(n*n), 空间复杂度O(1)。

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        int ret=0;
        for (int i=0; i<len; i++)
        {
            for (int j=i+1; j<len; j++)
            {
                long long ans = hours[i]+hours[j];
                if (ans % 24 == 0)
                {
                    ret++;
                }
            }
        }
        return ret;
    }
};

 前面只是上课前赶时间写的，而很明显这个题目应该还有可以优化的地方，平方的复杂度还是有点高了。那么有什么办法可以优化一下呢？可以这样想，我们的i已经确定了，那么要找的j就是固定加起来是24的倍数的。那是不是可以想办法记录一下每个数和哪些数加起来是24的倍数呢。当然可以，给每个数对24取余一下就可以了，而和它组成的24倍数的就是取余后和为24的。这一点应该能够理解。这样就得到了一个改进版的代码了，实际上这也就是哈希了

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        vector<vector<int> > vec(24);
        for (int i=0; i<len; i++)
        {
            int mod = hours[i]%24;
            vec[mod].push_back(hours[i]);
        }
        int ans=0;
        for (int i=1; i<12; i++)
        {
            ans += (vec[i].size())*(vec[24-i].size());
        }
        int mod0 = vec[0].size(), mod12 = vec[12].size();
        ans += mod0*(mod0-1)/2;
        ans += mod12*(mod12-1)/2;
        return ans;
    }
};

取余为0和取余为12的需要特判一下，因为和它们配对的数的取余值就是自己。

这样就把两重循环变成了一重循环，但增加了一个vec数组用来记录每个数取余后所在的位置。

时间复杂度O(n), 空间复杂度O(n)。

那么，还有办法可以继续优化吗？时间复杂度肯定是降不下去了，毕竟不管怎么改，总得遍历一次吧。但空间复杂度说不定还可以优化一下。

确实可以，我们可以注意到，我们虽然在vec里把每个数都存了起来，但实际上我们并没有用到它们。我们只是用到了数量。那么我们完全可以选择不存这些数，而只记录一下取余后的值的数量。

这样我们就得到了下一版的代码了

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        map<int, int> ma;
        for (int i=0; i<len; i++)
        {
            ma[hours[i]%24]++;
        }
        int ma0=ma[0], ma12=ma[12];
        int ans = ma0*(ma0-1)/2;
        ans += ma12*(ma12-1)/2;
        for (int i=1; i<12; i++)
        {
            ans += ma[i]*ma[24-i];
        }
        return ans;
    }
};

思路与之前一致，只是少存了没用的数了，顺便这里的map完全可以用一个数组代替，我只是太久没写代码了，用下map熟悉一下而已

时间复杂度还是O(n)，但空间复杂度降到了O(1)。

这应该就是最终版了，至少我想不到其他的优化方法了

翻了下力扣的题解，我又找到了一个优化方法。其实也不算优化吧，因为时空复杂度都不变，只不过也许可能大概常数因子会稍微小一点，因为把乘法换成了加法，也少了一次循环，但多了取余

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int ans = 0;
        int cnt[24];
        memset(cnt, 0, sizeof(cnt));//也许换成循环会更快一点点？
        for (int h : hours)
        {
            int mod = h%24;
            ans += cnt[(24-mod)%24];
            cnt[mod]++;
        }
        return ans;
    }
};

特别提醒一句，cnt[(24-mod)%24]里面的取余是必不可少的，不然mod为0的时候就会数组越界了。而且两个加法的顺序也不能换，不然就多算了