LeetCode-3185 构成整天的下标对数目Ⅱ
今天的每日一题是昨天的升级版,昨天的数据量比较小直接暴力就完事了,今天数据量上升,暴力就不行了。
题目简单翻译一下就是找出从数组里找出俩数,相加的和正好可以被24整除,一共可以找出几对。
暴力解法就是两两相加取余,昨天的题直接暴力甚至时间复杂度可以跑到100%
今天的题目一看就不能暴力,所以我没去试。
两个数相加的和能被24整除,那么表示这俩数分别取余24的结果相加还可以被24整除。
所以我们可以把数组里的数全部取余24,余数相同的数我们完全可以把它们当成是同一个数,这样就可以把很多个数据给分为24种(0~23)
假设余数为1的数有n个,而余数为23的数有m个,那么这两批数是可以两两配对的,所以得到的下标对是n*m
同理,余数为2的数就找余数为22的,以此类推……
但是有个小细节,那就是余数为0和余数为12的是特例,因为它们是和自己本身这种类型的数进行配对的,这就需要用到高中数学的排列组合了(我忘了,百度的)。
假设它们自身个数是n,那么两两配对(不重复)的组合数就是(n*(n-2)/ 2)。
class Solution {
public:long long countCompleteDayPairs(vector<int>& hours) {long long res = 0;unordered_map<int,long>cache;for(int& h:hours) cache[h%24]++;for(int i = 1; i < 12; ++i) res += (cache[i] * cache[24 - i]);// 0和12需要单独计算,因为是自身两两配对res += (cache[0] * (cache[0] - 1)) / 2;res += (cache[12] * (cache[12] - 1)) / 2;return res;}
};