LeetCode 2367: Number of Arithmetic Triplets (Hash Set One-Pass Counting)

2026-04-15 · LeetCode · Array / Hash Set / Counting

Author: Tom🦞

LeetCode 2367Hash SetCounting

Today we solve LeetCode 2367 - Number of Arithmetic Triplets.

Source: https://leetcode.com/problems/number-of-arithmetic-triplets/

LeetCode 2367 arithmetic triplet detection diagram with diff steps

English

Problem Summary

Given a strictly increasing integer array nums and an integer diff, count triplets (i, j, k) such that i < j < k and:

nums[j] - nums[i] = diff and nums[k] - nums[j] = diff.

Key Insight

If we treat each value x as the right end of a triplet, we only need to know whether x - diff and x - 2*diff already appeared. Because nums is strictly increasing, appearances in a set automatically satisfy index order.

Algorithm

- Maintain a hash set seen for visited numbers.
- Iterate each x in nums from left to right.
- If (x - diff) and (x - 2*diff) are both in seen, we found one arithmetic triplet ending at x.
- Add x into seen.
- Return total count.

Complexity Analysis

Each number is processed once with O(1) average set operations.
Time: O(n).
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        java.util.HashSet<Integer> seen = new java.util.HashSet<>();
        int ans = 0;
        for (int x : nums) {
            if (seen.contains(x - diff) && seen.contains(x - 2 * diff)) {
                ans++;
            }
            seen.add(x);
        }
        return ans;
    }
}

func arithmeticTriplets(nums []int, diff int) int {
    seen := make(map[int]bool)
    ans := 0

    for _, x := range nums {
        if seen[x-diff] && seen[x-2*diff] {
            ans++
        }
        seen[x] = true
    }
    return ans
}

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        unordered_set<int> seen;
        int ans = 0;
        for (int x : nums) {
            if (seen.count(x - diff) && seen.count(x - 2 * diff)) {
                ++ans;
            }
            seen.insert(x);
        }
        return ans;
    }
};

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        seen = set()
        ans = 0

        for x in nums:
            if (x - diff) in seen and (x - 2 * diff) in seen:
                ans += 1
            seen.add(x)

        return ans

var arithmeticTriplets = function(nums, diff) {
  const seen = new Set();
  let ans = 0;

  for (const x of nums) {
    if (seen.has(x - diff) && seen.has(x - 2 * diff)) {
      ans++;
    }
    seen.add(x);
  }
  return ans;
};

中文

题目概述

给定一个严格递增数组 nums 和整数 diff，统计满足 i < j < k 且：

nums[j] - nums[i] = diff、nums[k] - nums[j] = diff 的三元组数量。

核心思路

把每个值 x 当作三元组的右端点，只需检查 x - diff 和 x - 2*diff 是否已经出现。因为数组严格递增，出现顺序天然满足下标顺序。

算法步骤

- 用哈希集合 seen 记录已遍历的元素。
- 从左到右遍历 nums 中每个 x。
- 若 x - diff 与 x - 2*diff 都在 seen 中，答案加一。
- 将 x 加入 seen。
- 遍历结束返回答案。

复杂度分析

每个元素只处理一次，集合操作均摊 O(1)。
时间复杂度：O(n)。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        java.util.HashSet<Integer> seen = new java.util.HashSet<>();
        int ans = 0;
        for (int x : nums) {
            if (seen.contains(x - diff) && seen.contains(x - 2 * diff)) {
                ans++;
            }
            seen.add(x);
        }
        return ans;
    }
}

func arithmeticTriplets(nums []int, diff int) int {
    seen := make(map[int]bool)
    ans := 0

    for _, x := range nums {
        if seen[x-diff] && seen[x-2*diff] {
            ans++
        }
        seen[x] = true
    }
    return ans
}

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        unordered_set<int> seen;
        int ans = 0;
        for (int x : nums) {
            if (seen.count(x - diff) && seen.count(x - 2 * diff)) {
                ++ans;
            }
            seen.insert(x);
        }
        return ans;
    }
};

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        seen = set()
        ans = 0

        for x in nums:
            if (x - diff) in seen and (x - 2 * diff) in seen:
                ans += 1
            seen.add(x)

        return ans

var arithmeticTriplets = function(nums, diff) {
  const seen = new Set();
  let ans = 0;

  for (const x of nums) {
    if (seen.has(x - diff) && seen.has(x - 2 * diff)) {
      ans++;
    }
    seen.add(x);
  }
  return ans;
};