526互联

力扣---2367. 算术三元组的数目

发布时间 2023-03-31 15:59:09作者: Owlwu

2367. 算术三元组的数目

难度简单

给你一个下标从 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 严格 递增

暴力，寻找，哈希表，三指针，二分查找啥的都能做。最好用的就是哈希表和三指针。

三指针基础思路版：

由于数组递增，可以想到假设y大于x，那么y - diff 大于x - diff，y + diff 大于x + diff。

利用三指针分别指向即可。

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        int res = 0;
        for (int i = 0; i < nums.length; i ++) {
            // 左边等于nums[i] - diff的元素的数目。
            // 右边等于nums[i] + diff的元素的数目。
            int res1 = 0;
            int res2 = 0;
            int tem1 = nums[i] - diff;
            int tem2 = nums[i] + diff;
            // 寻找左边等于tem1的元素的数量。
            for (int j = 0; nums[j] <= tem1; j ++) {
                if (nums[j] == tem1) {
                    res1 ++;
                }
            }
            // 寻找右边等于tem2的元素的数量。
            for (int j = i; j < nums.length && nums[j] <= tem2; j ++) {
                if (nums[j] == tem2) {
                    res2 ++;
                }
            }
            // 两者相乘即是当前元素符合题意的三元组数目。
            res += res1 * res2;
        }
        return res;
    }
}

 

 

哈希表：

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        int res = 0;
        for (int x : nums) {
            if (set.contains(x - diff) && set.contains(x + diff)) {
                res ++;
            }
        }
        return res;
    }
}

 

 三指针：

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        int res = 0;
        int n = nums.length;
        for (int i = 0, j = 1, k = 2; i < n - 2 && j < n - 1 && k < n; i++) {
            j = Math.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 = Math.max(k, j + 1);
            while (k < n && nums[k] - nums[j] < diff) {
                k++;
            }
            if (k < n && nums[k] - nums[j] == diff) {
                res++;
            }
        }
        return res;
    }
}