算术三元组的数目

标签: 数组 哈希表 双指针 枚举

难度: Easy

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ：

  • i < j < k ，
  • nums[j] - nums[i] == diff 且
  • nums[k] - nums[j] == diff

返回不同 算术三元组 的数目。

示例 1：

输入：nums = [0,1,4,6,7,10], diff = 3
输出：2
解释：
(1, 2, 4) 是算术三元组：7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组：10 - 7 == 3 且 7 - 4 == 3 。

示例 2：

输入：nums = [4,5,6,7,8,9], diff = 2
输出：2
解释：
(0, 2, 4) 是算术三元组：8 - 6 == 2 且 6 - 4 == 2 。
(1, 3, 5) 是算术三元组：9 - 7 == 2 且 7 - 5 == 2 。

提示：

  • 3 <= nums.length <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums 严格 递增

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        tset = set(nums)
        nm = 0
        ln = len(nums)
        for i in range(ln - 2):
            tmp = nums[i]
            if (tmp + diff in tset) and (tmp + diff + diff in tset):
                nm += 1
        return nm

Explain

题解的核心思路是利用哈希集合来快速查询数组中是否存在特定的元素。首先，将所有元素存入一个集合 `tset`，这样可以在常数时间内判断一个元素是否存在于数组中。遍历数组，对于每个元素 `nums[i]`，检查 `nums[i] + diff` 和 `nums[i] + 2 * diff` 是否也在集合中。如果都在，那么 `(i, j, k)` 形成一个有效的算术三元组。由于数组是严格递增的，保证了 `i < j < k` 的条件自然满足。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        tset = set(nums)  # 将数组元素放入集合中以便快速查找
        nm = 0  # 用于计数有效的算术三元组
        ln = len(nums)  # 计算数组的长度
        for i in range(ln - 2):  # 遍历到倒数第三个元素即可，因为需要形成三元组
            tmp = nums[i]  # 当前元素
            if (tmp + diff in tset) and (tmp + diff + diff in tset):  # 检查两个条件是否满足
                nm += 1  # 如果满足，则计数器增加
        return nm  # 返回计数结果

Explore

在算法中使用哈希集合（set）而不是数组或链表的主要原因是哈希集合能够提供平均时间复杂度为O(1)的元素查找效率。当需要频繁地检查某个元素是否存在于集合中时，哈希集合比数组（查找时间复杂度为O(n)）或链表（同样是O(n)）更有效率。此外，哈希集合通过散列函数直接访问元素，不需要像数组或链表那样进行线性搜索，这在元素数量较大时尤其重要。

只遍历到数组的倒数第三个元素是足够的，这种做法不会漏掉任何有效的三元组。因为每个有效的三元组由三个元素组成，我们在查找每个元素对应的后两个元素时，如果当前元素是数组中的最后一个或倒数第二个，则不可能找到两个符合条件的后续元素。因此，只需要遍历到倒数第三个元素，保证每次查找都有足够的后续元素来形成三元组。

在哈希集合中，常数时间的成员检查是通过哈希表实现的。哈希表通过使用散列函数将集合中的每个元素映射到哈希表的一个位置（即桶）。当检查一个元素是否存在于集合中时，哈希函数计算该元素的哈希值，并直接定位到对应的桶。如果该位置存储了目标元素，则表示元素存在；否则不存在。虽然哈希冲突会导致查找时间变长，但平均情况下这个时间仍然是常数O(1)。