leetcode 2367. number of arithmetic triplets【哈希表,三指针】简单-爱代码爱编程
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
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 < j < k
,nums[j] - nums[i] == diff
, andnums[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]−2⋅diff,nums[k]−diff,nums[k])
所以还可以一边查询哈希表中是否有
n
u
m
s
[
k
]
−
2
⋅
d
i
f
f
nums[k]−2⋅diff
nums[k]−2⋅diff 和
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]+diff≥x ;
- 如果 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]+2⋅diff≥x ;
- 如果 n u m s [ i ] + 2 ⋅ d i f f = x nums[i]+2⋅diff=x nums[i]+2⋅diff=x ,则找到了一对等差三元组。
注意,下面代码在循环时没有判断 i < j i< j i<j 和 j < k j<k j<k ,因为一旦 j ≥ k j \ge k j≥k , n u m s [ j ] + d i f f ≥ x nums[j]+diff≥x nums[j]+diff≥x 必然成立,所以 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) ,仅用到若干额外变量。