代码编织梦想

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

You are given a 0-indexedstrictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:

  • i < j < k,
  • nums[j] - nums[i] == diff, and
  • nums[k] - nums[j] == diff.

Return the number of unique arithmetic triplets.

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3. 

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

Constraints:

  • 3 <= nums.length <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums is strictly increasing.

题意:给出一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 等差三元组 :

  • i < j < k ,
  • nums[j] - nums[i] == diff 且
  • nums[k] - nums[j] == diff

返回不同 等差三元组 的数目。


解法1 哈希集合

arithmetic triplets 应翻译成等差三元组(如 arithmetic progression 翻译成等差数列)。

由于 nums \textit{nums} nums 是严格递增的,即没有重复元素,对于一个特定且唯一的 nums [ j ] \textit{nums}[j] nums[j] ,如果它在等差三元组中,那么这样的等差三元组是唯一的,即 ( nums [ j ] − diff ,   nums [ j ] ,   nums [ j ] + diff ) (\textit{nums}[j]-\textit{diff},\ \textit{nums}[j],\ \textit{nums}[j]+\textit{diff}) (nums[j]diff, nums[j], nums[j]+diff)
可用哈希集合记录 nums \textit{nums} nums 的每个元素,然后遍历 nums \textit{nums} nums ,看 n u m s [ j ] − d i f f nums[j]−diff nums[j]diff n u m s [ j ] + d i f f nums[j]+diff nums[j]+diff 是否都在哈希集合中。

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0;
        unordered_set<int> rec(nums.begin(), nums.end());
        for (int i = 0, n = nums.size(); i < n; ++i)
            if (rec.find(nums[i] - diff) != rec.end()
                && rec.find(nums[i] + diff) != rec.end())
                ++ans;
        return ans;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n nums \textit{nums} nums 的长度。
  • 空间复杂度: O ( n ) O(n) O(n)

优化:等差三元组可以用 n u m s [ k ] nums[k] nums[k] 表示:
( n u m s [ k ] − 2 ⋅ d i f f , n u m s [ k ] − d i f f , n u m s [ k ] ) (nums[k]−2⋅diff,nums[k]−diff,nums[k]) (nums[k]2diff,nums[k]diff,nums[k])
所以还可以一边查询哈希表中是否有 n u m s [ k ] − 2 ⋅ d i f f nums[k]−2⋅diff nums[k]2diff n u m s [ k ] − d i f f nums[k]−diff nums[k]diff ,一边把 n u m s [ k ] nums[k] nums[k] 插入哈希表,从而做到一次遍历

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0;
        unordered_set<int> rec;
        for (int i = 0, n = nums.size(); i < n; ++i) {
            if (rec.find(nums[i] - 2 * diff) != rec.end()
                && rec.find(nums[i] - diff) != rec.end())
                ++ans;
            rec.insert(nums[i]);
        }
        return ans;
    }
};

解法2 同向三指针

由于 n u m s nums nums 是严格递增的,遍历 k k k 时, i i i j j j 只增不减,因此可以用类似同向双指针的做法来移动指针:

  • 枚举 x = n u m s [ k ] x=nums[k] x=nums[k]
  • 移动 j j j 直到 n u m s [ j ] + d i f f ≥ x nums[j]+diff≥x nums[j]+diffx
  • 如果 n u m s [ j ] + d i f f = x nums[j]+diff=x nums[j]+diff=x ,则移动 i i i 直到 n u m s [ i ] + 2 ⋅ d i f f ≥ x nums[i]+2⋅diff≥x nums[i]+2diffx
  • 如果 n u m s [ i ] + 2 ⋅ d i f f = x nums[i]+2⋅diff=x nums[i]+2diff=x ,则找到了一对等差三元组。

注意,下面代码在循环时没有判断 i < j i< j i<j j < k j<k j<k因为一旦 j ≥ k j \ge k jk n u m s [ j ] + d i f f ≥ x nums[j]+diff≥x nums[j]+diffx 必然成立,所以 j < k j<k j<k 无需判断 i i i 也同理。

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0, i = 0, j = 1; 
        for (int x : nums) {
            while (nums[j] + diff < x) ++j; // 直到nums[j]+diff>=x
            if (nums[j] + diff != x) continue;
            while (nums[i] + diff < nums[j]) ++i;
            if (nums[i] + diff == nums[j]) ++ans;
        }
        return ans;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n n u m s nums nums 的长度。虽然写了个二重循环,但 i + + i++ i++ j + + j++ j++ 的执行次数不会超过 n n n 次,所以总的时间复杂度为 O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1) ,仅用到若干额外变量。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/myRealization/article/details/129891839

leetcode 191. number of 1 bits_spade_的博客-爱代码爱编程

191. Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1’ bits it has

leetcode 200. number of islands_spade_的博客-爱代码爱编程

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by wat

LeetCode1002. 查找常用字符(哈希表、count)-爱代码爱编程

1、题目描述 https://leetcode-cn.com/problems/find-common-characters/ 给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。 例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。 你可以按任意

⭐算法入门⭐《哈希表》中等01 —— LeetCode 525. 连续数组-爱代码爱编程

🙉饭不食,水不饮,题必须刷🙉 C语言免费动漫教程,和我一起打卡! 🌞《光天化日学C语言》🌞 LeetCode 太难?先看简单题! 🧡《C语言入门100例》🧡 数据结构难?不存在的! 🌳《画解数据结构》🌳 LeetCode 太简单?算法学起来!

⭐算法入门⭐《哈希表》简单02 —— LeetCode 41. 缺失的第一个正数-爱代码爱编程

🙉饭不食,水不饮,题必须刷🙉 C语言免费动漫教程,和我一起打卡! 🌞《光天化日学C语言》🌞 LeetCode 太难?先看简单题! 🧡《C语言入门100例》🧡 数据结构难?不存在的! 🌳《画解数据结构》🌳 LeetCode 太简单?算法学起来!

Leetcode454.四数相加(哈希表 分组 C++)-爱代码爱编程

Leetcode454.四数相加(哈希表 分组 C++) 题目描述:示例知识点思路代码思路来源 题目描述: 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 <= i, j, k, l < n nums1[i] + nums2

Leetcode160.相交链表(哈希集合/双指针,C++)-爱代码爱编程

*此题借鉴Leetcode官方题解 题目描述: 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 思路1:哈希集合——首先我们可以想到,如果我们把链表A存到数组里面,再对B进行遍历,同时与数组对比,即可完成提

Leetcode 2125. Number of Laser Beams in a Bank [Python]-爱代码爱编程

计算每行的1的数量,每两层之间的连线数量就是两层1的数量的乘积。 class Solution: def numberOfBeams(self, b: List[str]) -> int: line = [] for row in b: acc = 0 for

leetcode 2367. number of arithmetic triplets-爱代码爱编程

You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met: i