c++ 构成整天的下标对数目 leetcode

目录

一、leetcode 3184.构成 整天 的下标对数目I

1.问题描述

 2.方法：暴力穷举

二、leetcode 3185.构成 整天 的下标对数目 II

1.问题描述

2.方法：哈希表

一、leetcode 3184.构成 整天 的下标对数目I

1.问题描述

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

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

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

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

• 1 <= hours.length <= 100
• 1 <= hours[i] <= 109

 2.方法：暴力穷举

int countCompleteDayPairs(vector<int>& hours) {
        int size=hours.size();
        int count=0;
        for(int i=0;i<size-1;i++)
        {
            for(int j=i+1;j<size;j++)
            {
                if((hours[i]+hours[j])%24==0)
                {
                    count++;
                }
            }
        }
        return count;
    }

二、leetcode 3185.构成 整天 的下标对数目 II

1.问题描述

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

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

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

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

• 1 <= hours.length <= 5 * 105
• 1 <= hours[i] <= 109

2.方法：哈希表

如果穷举的话，时间复杂度为O(n^2)，会超时。

（1）考虑用哈希表，第一个值存储hours[i]%24的余数temp，第二个值存储该余数出现的次数。

（2）对于每个hours[i]，都在mymap里查找有没有能构成整天的余数，并且count+=该余数出现的次数。

（3）对于每个hours[i]，都在mymap里查找有没有该余数，如果没有就插入该余数，此时该余数第一次出现，第二个值为1；若有该余数，那么该余数出现次数++，即第二个值++。

long long countCompleteDayPairs(vector<int>& hours) {
        long long int count=0;
        map<int,int> mymap;
        map<int,int>::iterator it;
        int size=hours.size();
        int temp=0;
        for(int i=0;i<size;i++)
        {
            temp=hours[i]%24;
            if(temp!=0)
            {
                it=mymap.find(24-temp);
            }
            else it=mymap.find(0);
            if(it!=mymap.end())
            {
                count+=(it->second);
            }
            it=mymap.find(temp);
            if(it!=mymap.end())
            {
                (it->second)++;
            }
            else mymap.insert(map<int,int>::value_type(temp,1));
        }
        return count;
    }