【LeetCode】算术三元组的数目 Java 题解

作者：Albert

2022 年 8 月 07 日
本文字数：1239 字
阅读完需：约 4 分钟

题目描述

给你一个下标从 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 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/number-of-arithmetic-triplets著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

解题思路

今天的算法题目是数组题目，题目自定义了一组算术三元组计算规则，我们需要计算出不同的算术三元组数目。
算术三元组的计算规则是定义好的，我们首先可以使用模拟的算法解决，时间复杂度是 O(n * n * n), 这种解法可以优化的每一层计算的个数，可以提升部分计算效率。
再次分析题目和代码，题目给出的数据是严格递增的数据，且 diff 是正整数，因此，我们可以直接枚举 j 的取值，然后分别查询 nums[j] - diff 和 nums[j] + diff 是否在数组中即可。这样思维转化之后，就和两数之和相似，我们可以使用 HashSet 集合记录出现的所有数值，使用 contains 方法判断 nums[j] - diff 和 nums[j] + diff 是否存在。如果都存在，就是一个答案。具体实现代码如下，供参考。

代码

模拟解法

class Solution {    public int arithmeticTriplets(int[] nums, int diff) {        int ans = 0;        int n = nums.length;        for (int i = 0; i < n - 2; i++) {            for (int j = i + 1; j < n - 1; j++) {                if (nums[j] - nums[i] == diff) {                    for (int k = j + 1; k < n; k++) {                        if (nums[k] - nums[j] == diff) {                            ans++;                        }                    }                }
            }        }                return ans;    }}

复制代码

HashSet 解法

class Solution {    public int arithmeticTriplets(int[] nums, int diff) {        int ans = 0;        Set<Integer> set = new HashSet<>();        int n = nums.length;        for (int i = 0; i < n; i++) {            set.add(nums[i]);        }        for (int j = 1; j < n - 1; j++) {            if (set.contains(nums[j] - diff) && set.contains(nums[j] + diff)) {                ans++;            }        }
        return ans;    }}