LeetCode 2367. 算术三元组的数目_给你一个下标从 0 开始、严格递增 的整数数组 a 和一个正整数 tar 。如果满足下述

给你一个下标从 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 。

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

解法一：遍历输入数组nums，并准备两个指针left和right，遍历nums中的每个数字i时，让指针left指向数字i左边与i相减的差小于等于diff的首个数字上，让指针right指向数字i右边与i相减的差小于等于diff的首个数字上，然后看left、i、right是否构成算术三元组。由于数组是严格递增的，因此left和right只需要增大，不需要减小：

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        if (nums.size() < 3) {
            return 0;
        }

        vector<int>::iterator left = nums.begin();
        vector<int>::iterator right = nums.begin() + 1;

        int ret = 0;
        for (int i : nums) {
            while (right != nums.end() && *right - i < diff) {
                ++right;
            }

            if (right == nums.end()) {
                --right;
            }

            while (i - *left > diff) {
                ++left;
            }

            if (*right - i == diff && i - *left == diff) {
                ++ret;
            }
        }

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

如果输入数组的元素数量为n，此解法时间复杂度为O（n），空间复杂度为O（1）。

解法二：创建一个哈希表，由于数组是严格递增的，因此数组中不会有相同的数字，我们可以把每个数字放到哈希表中，然后遍历一遍哈希表即可：

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        if (nums.size() < 3) {
            return 0;
        }

        vector<bool> hashTbl(201, 0); 
        for (int i : nums) {
            hashTbl[i] = true;
        }

        int ret = 0;
        for (int i = 0; i < 201 - diff * 2; ++i) {
            if (hashTbl[i] && hashTbl[i + diff] && hashTbl[i + 2 * diff]) {
                ++ret;
            }
        }
        
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果输入数组的元素数量为n，每个元素的范围为m，此解法时间复杂度O（n+m），空间复杂度O（m）。

解法三：暴力枚举：

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        if (nums.size() < 3) {
            return 0;
        }

        int ret = 0;
        int size = nums.size();
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                for (int k = 0; k < size; ++k) {
                    if (nums[k] - nums[j] == diff && nums[j] - nums[i] == diff) {
                        ++ret;
                    }
                }
            }
        }

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果输入数组的元素数量为n，此解法时间复杂度为O（n³），空间复杂度为O（1）。