Leetcode每日一题-20241023

原题链接：构成整天的下标对数目II

这题有个简单版本，但是要明确这题需要用什么方法做出来，就不能像简单题那样粗暴的循环计算。这和做过的两数之和有些类似，只是这题是整数倍，可以首先把Hours数组都按24取余，并不会影响计算结果。使用哈希表记录每个值的索引，然后再计算符合24整数倍的数对中，符合索引大小条件的个数有多少即可。

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        h = [x % 24 for x in hours]
        h_map = {}
        for i, y in enumerate(h):
            if y not in h_map:
                h_map[y] = [i]
            else:
                h_map[y].append(i)
        ans = 0
        visited = set()
        for hour, idx_lis in h_map.items():
            if (hour == 0) or (hour == 12):
                if len(idx_lis) > 1:
                    ans += len(idx_lis) * (len(idx_lis) - 1) // 2
            else:
                if ((24 - hour) in h_map) and ((24 - hour) not in visited):
                    other_lis = h_map[24 - hour]
                    i, j = 0, 0
                    n1, n2 = len(idx_lis), len(other_lis)
                    while (i < n1) and (j < n2):
                        if idx_lis[i] < other_lis[j]:
                            ans += n2 - j
                            i += 1
                        else:
                            ans += n1 - i
                            j += 1
                    visited.add(hour)
        return ans

上面还用到visited来记录已经计算过的数对，以避免重复计算。而当我看了题解后，顿感这太繁琐了。贴一下题解：

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        ans = 0
        cnt = [0] * 24
        for hour in hours:
            ans += cnt[(24 - hour % 24) % 24]
            cnt[hour % 24] += 1
        return ans

这真的是很优雅的解法，cnt为计数的数组，顺序遍历hours数组时保证了数对是符合i < j的条件的，不需要多考虑数对重复计算的情况，真的很妙。