Skip to content

Latest commit

 

History

History
81 lines (74 loc) · 2.98 KB

README.md

File metadata and controls

81 lines (74 loc) · 2.98 KB

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.

Related Topics:
Array, Hash Table, Two Pointers, Enumeration

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/number-of-arithmetic-triplets
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int arithmeticTriplets(vector<int>& A, int diff) {
        int N = A.size(), ans = 0;
        unordered_set<int> s(begin(A), end(A));
        for (int n : A) {
            ans += s.count(n + diff) && s.count(n + 2 * diff);
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/number-of-arithmetic-triplets
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int arithmeticTriplets(vector<int>& A, int diff) {
        int N = A.size(), ans = 0, i = 0, j = 1, k = 2;
        for (; i < N; ++i) {
            while (j < N && A[j] < A[i] + diff) ++j;
            while (k < N && A[k] < A[i] + 2 * diff) ++k;
            if (j < N && k < N && A[j] == A[i] + diff && A[k] == A[i] + 2 * diff) ++ans;
        }
        return ans;
    }
};