Leetcode(每日一题)——2367. 算术三元组的数目_leetcode 算术三元组的数目

摘要

2367. 算术三元组的数目

一、暴力解析

了得到算术三元组的数目，最直观的做法是使用三重循环暴力枚举数组中的每个三元组，判断每个三元组是否为算术三元组，枚举结束之后即可得到算术三元组的数目。

/**
     * @description 采用暴力的解析 
      * @param: nums
     * @param: diff
     * @date: 2023/3/31 7:37
     * @return: int
     * @author: xjl
    */
    public int arithmeticTriplets0(int[] nums, int diff) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] - nums[i] != diff) {
                    continue;
                }
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] - nums[j] == diff) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }

复杂度分析

• 时间复杂度：O(n^3)，其中 nn 是数组 nums的长度。使用三重循环暴力枚举需要O(n^3) 的时间。
• 空间复杂度：O(1)。只需要常数的额外空间。

二、利用Hash算法解析

由于给定的数组 nums是严格递增的，因此数组中不存在重复元素，不存在两个相同的算术三元组。对于数组nums中的元素x，如果x+diff和 x+2×diff都在数组中，则存在一个算术三元组，其中的三个元素分别是 x、x+diff和 x+2×diff，因此问题转换成计算数组 nums中有多少个元素可以作为算术三元组的最小元素。为了快速判断一个元素是否在数组中，可以使用哈希集合存储数组中的所有元素，然后判断元素是否在哈希集合中。将数组中的所有元素都加入哈希集合之后，遍历数组并统计满足 x+diff和 x+2×diff都在哈希集合中的元素x的个数，即为算术三元组的数目。

    /**
     * @description 这样的一种的是更为简单就是保证两个树都在list里面
      * @param: nums
     * @param: diff
     * @date: 2023/3/31 7:22
     * @return: int
     * @author: xjl
    */
    public int arithmeticTriplets2(int[] nums, int diff) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            set.add(x);
        }
        int ans = 0;
        for (int x : nums) {
            if (set.contains(x + diff) && set.contains(x + 2 * diff)) {
                ans++;
            }
        }
        return ans;
    }

复杂度分析

• 时间复杂度：O(n)，其中 nn 是数组 numsnums 的长度。需要遍历数组两次，每次将元素加入哈希集合与判断元素是否在哈希集合中的时间都是 O(1)。
• 空间复杂度：O(n)，其中 nn 是数组 nums的长度。哈希集合需要O(n) 的空间。

三、采用三指针解析

用 i、j和 k分别表示三元组的三个下标，其中 i<j<k，初始时 i=0，j=1，k=2。对于每个下标i，最多有一个下标 j和一个下标 k使得 (i,j,k)是算术三元组。假设存在两个算术三元组 (i1,j1,k1)和 (i2,j2,k2)满足 i1<i2，则根据数组nums严格递增可以得到 nums[i1]<nums[i2]，因此有 nums[j1]<nums[j2]和 nums[k1]<nums[k2]，下标关系满足 j1<j2和 k1<k2​。由此可以得到结论：如果 (i,j,k)是算术三元组，则在将i增加之后，为了得到以i作为首个下标的算术三元组，必须将j和k也增加。利用上述结论，可以使用三指针统计算术三元组的数目。

从小到大枚举每个i，对于每个i，执行如下操作。

• 定位 j。
•       为了确保 j>i，如果 j≤i则将 j更新为 i+1。
•       如果 j<n−1且 nums[j]−nums[i]<diff，则只有将j向右移动才可能满足 nums[j]−nums[i]=diff，因此将 j向右移动，直到 j≥n−1或 nums[j]−nums[i]≥diff。如果此时 j≥n−1或nums[j]−nums[i]>diff，则对于当前的i不存在 j和 k可组成算术三元组，因此继续枚举下一个i。
• 当 j<n−1且 nums[j]−nums[i]=diff时，定位k。
•        为了确保 k>j，如果k≤j则将 k更新为j+1。
•        如果 k<n且 nums[k]−nums[j]<diff，则只有将 k向右移动才可能满足 nums[k]−nums[j]=diff，因此将 k向右移动，直到 k≥n或 nums[k]−nums[j]≥diff。如果此时 k<n且 nums[k]−nums[j]=diff，则当前的 (i,j,k)是算术三元组。

/**
     * @description 采用的是三指针的方式来实现 减少了的存的空间 直接使用的数组来判断下标的是否在数组中，如果在那就是存储，如果是不存在，那就是不存在
      * @param: nums
     * @param: diff
     * @date: 2023/3/31 7:27
     * @return: int
     * @author: xjl
    */
    public int arithmeticTriplets3(int[] nums, int diff) {
        int ans = 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) {
                ans++;
            }
        }
        return ans;
    }

复杂度分析

• 时间复杂度：O(n)，其中n是数组 nums的长度。三个指针最多各遍历数组一次。
• 空间复杂度：O(1)。只需要常数的额外空间。

博文参考

《leetcode》