2367. 等差三元组的数目

🟢   🔖  数组 哈希表 双指针 枚举  🔗 力扣 LeetCode

题目

You are given a 0-indexed , strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:

• i < j < k,
• nums[j] - nums[i] == diff, and
• nums[k] - nums[j] == diff.

Return the number of unique arithmetic triplets.

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3

Output: 2

Explanation:

(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.

(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2

Output: 2

Explanation:

(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.

(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

Constraints:

• 3 <= nums.length <= 200
• 0 <= nums[i] <= 200
• 1 <= diff <= 50
• nums is strictly increasing.

题目大意

给你一个下标从 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 严格 递增

解题思路

1. 将数组元素存入 Set，以便快速查找。
2. 遍历数组中的每个元素 nums[i]，判断 nums[i] + diff 和 nums[i] + diff * 2 是否存在，如果这两个元素都存在，就可以组成一个等差三元组。
3. 如果找到符合条件的三元组，计数器 res 加一。
4. 返回最终计数器的值。

复杂度分析

• 时间复杂度：O(n)，构建 Set 和遍历数组检查是否存在两个值构成等差三元组，时间复杂度都为 O(n)
• 空间复杂度：O(n)，使用了一个额外的 Set 存储数组元素。

代码

/**
 * @param {number[]} nums
 * @param {number} diff
 * @return {number}
 */
var arithmeticTriplets = function (nums, diff) {
	let set = new Set(nums); // 使用 Set 存储数组元素
	let res = 0; // 初始化结果计数器

	for (let i = 0; i < nums.length; i++) {
		// 检查 nums[i] + diff 和 nums[i] + diff * 2 是否在集合中
		if (set.has(nums[i] + diff) && set.has(nums[i] + diff * 2)) {
			res++; // 满足条件的三元组计数 +1
		}
	}

	return res; // 返回最终结果
};

相关题目

题号	标题	题解	标签	难度	力扣
1	两数之和	[✓]	数组 哈希表	🟢	🀄️ 🔗
15	三数之和	[✓]	数组 双指针 排序	🟠	🀄️ 🔗
2475	数组中不等三元组的数目		数组 哈希表 排序	🟢	🀄️ 🔗
2873	有序三元组中的最大值 I		数组	🟢	🀄️ 🔗
2908	元素和最小的山形三元组 I		数组	🟢	🀄️ 🔗