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 严格递增

解题思路

这道题要求找到满足算术等差条件的三元组数量。根据题目要求，三元组 (i, j, k) 需满足 nums[j] - nums[i] == diff 且 nums[k] - nums[j] == diff，也就是 nums[i]、nums[j]、nums[k] 构成公差为 diff 的等差数列。

解法一：暴力枚举 最直接的方法是使用三重循环枚举所有可能的三元组。由于数组严格递增，我们只需要确保 i < j < k 即可。时间复杂度为 O(n³)，但考虑到数组长度最多 200，这种解法完全可行。

解法二：哈希表优化 利用哈希表存储所有数组元素，对于每个元素 nums[i]，检查 nums[i] + diff 和 nums[i] + 2*diff 是否都存在于数组中。如果存在，则找到一个算术三元组。这种方法时间复杂度降为 O(n)。

推荐解法：哈希表优化 由于数组元素范围和长度都较小，哈希表方法既简洁又高效。我们遍历数组，对于每个可能作为第一个元素的数，检查后续两个等差元素是否存在。

代码实现

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int count = 0;
        
        for (int num : nums) {
            if (numSet.count(num + diff) && numSet.count(num + 2 * diff)) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        num_set = set(nums)
        count = 0
        
        for num in nums:
            if num + diff in num_set and num + 2 * diff in num_set:
                count += 1
                
        return count

public class Solution {
    public int ArithmeticTriplets(int[] nums, int diff) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int count = 0;
        
        foreach (int num in nums) {
            if (numSet.Contains(num + diff) && numSet.Contains(num + 2 * diff)) {
                count++;
            }
        }
        
        return count;
    }
}

var arithmeticTriplets = function(nums, diff) {
    const numSet = new Set(nums);
    let count = 0;
    
    for (const num of nums) {
        if (numSet.has(num + diff) && numSet.has(num + 2 * diff)) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型暴力枚举哈希表优化（推荐）
时间复杂度O(n³)O(n)
空间复杂度O(1)O(n)

相关题目