LeetCode每日一题: 2367. 算术三元组的数目

题目链接：2367. 算术三元组的数目 - 力扣（Leetcode）
题目描述：给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ：

• i < j < k ，

• nums[j] - nums[i] == diff 且

• nums[k] - nums[j] == diff

返回不同 算术三元组 的数目。

这是一道easy级别的题目，看到这道题，第一反应是暴力破解，即一个三重循环求解，但是这种方法时间复杂度来到了O(n3)；

第二个想到的是类似于1. 两数之和 - 力扣（Leetcode）中的哈希表法

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

时间复杂度位O(n)，空间复杂度为O(n);

哈希表的作用是便于查找，而看到题目中给出的数组为有序数组，因此想到可以使用二分查找，这样就不需要额外空间，同时时间复杂度不会太高；

class Solution {
public:
    bool find(vector<int>& nums,int left,int target){
        int right=nums.size()-1;
        int mid;
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]==target){
                return true;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return false;
    }
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int n=nums.size();
        int res=0;
        for(int i=0;i<n;i++){
            if(find(nums,i,diff+nums[i])&&find(nums,i,2*diff+nums[i])){
                res++;
            }
        }
        return res;
    }
};

第四种方法就是官方题解给出的三指针法：

class Solution {
public:
    int arithmeticTriplets(vector& nums, int diff) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0, j = 1, k = 2; i < n - 2 && j < n - 1 && k < n; i++) {
            j = max(j, i + 1);
            while (j < n - 1 && nums[j] - nums[i] < diff) {
                j++;
            }
            if (j >= n - 1 || nums[j] - nums[i] > diff) {
                continue;
            }
            k = max(k, j + 1);
            while (k < n && nums[k] - nums[j] < diff) {
                k++;
            }
            if (k < n && nums[k] - nums[j] == diff) {
                ans++;
            }
        }
        return ans;
    }
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-arithmetic-triplets/solutions/2200026/suan-zhu-san-yuan-zu-de-shu-mu-by-leetco-ldq4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。