题目
给你一个下标从 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 <= 2000 <= nums[i] <= 2001 <= diff <= 50nums 严格 递增
分析题目
根据题目，我们可知现在有一个 严格递增 的数组，也就是正序数组 和 一个正整数的 diff 值，查找出满足 算术三元组 条件的个数。
那么算数三元组中的三个参数 (i, j, k) 是怎么来的呢？
根据以下定义：
i < j < k ,nums[j] - nums[i] == diff 且nums[k] - nums[j] == diff
按照(i, j, k) 的定义，我们可以确定 (nums[i + diff] == nums[j]) 且 ( nums[j + diff] == nums[k])
那么我们只需要以下标 k 为主要下标，每次查询 [k - diff] 存不存在即可判断是否满足下标 j 的条件，同理，确定下标 j 后，通过 [j - diff] 确定存不存在即可判断是否满足下标 i 的条件
方法1：哈希表
思路
根据上面的题目分析的结果，我们可以在每个下标再次进行 0 - k 之间的遍历，查找是否存在满足 j 条件的下标，当找到 j 时，在进行一次 0 - j 之间的遍历，查找是否有满足 i 条件的下标即可，那么我们为了减少循环次数，通过哈希表保存已经遍历到的元素，即可方便判断条件了。
具体实现
Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int arithmeticTriplets(int[] nums, int diff) {
int cnt = 0, n = nums.length;
Set<Integer> set = new HashSet<>();
for(int i = 0; i < n; i++) {
if(set.contains(nums[i] - diff)){
cnt += set.contains(nums[i] - diff * 2) ? 1 : 0;
}
set.add(nums[i]);
}
return cnt;
}
}
|
JavaScript 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| var arithmeticTriplets = function(nums, diff) {
const n = nums.length;
const set = new Set();
let cnt = 0;
for(let i = 0; i < n; i++) {
if(set.has(nums[i] - diff)){
cnt += set.has(nums[i] - diff * 2) ? 1 : 0;
}
set.add(nums[i]);
}
return cnt;
};
|
复杂度分析
- 时间复杂度：$O(n)$，其中
n 是数组 nums 的长度。每次将元素加入哈希集合与判断元素是否在哈希集合中的时间都是 $O(1)$。
- 空间复杂度：$O(n)$，其中
n 是数组 nums 的长度。哈希集合需要 $O(n)$ 的空间。
方法二：二分查找
思路
在方法一中，我们已经说明了暴力枚举法的解法：通过三个循环去判断每一项是否满足 (i, j, k) 的条件即可。
但是通过暴力枚举法的时间复杂度是 $O(n^3)$ , 那么我们有没有办法将搜索的时间复杂度降低呢？
答案是可以的，通过二分查找法对 j 和 i 进行定位，这样单个查找的时间复杂度就变为了 $O(log \ n)$
注意：理论上来讲 $O(n\ log\ n)$ 的算法要慢于 $O(n)$ 算法，但由于 LeetCode 的耗时统计不完全准确，并且测试用例的数据量没那么大，所以可能最终耗时反而比 $O(n)$ 算法耗时更短。
具体实现
Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int arithmeticTriplets(int[] nums, int diff) {
int cnt = 0, n = nums.length;
for(int i = 0; i < n; i++) {
int idx = binarySearch(nums, nums[i] - diff, i);
if(idx == -1 || nums[i] - diff - diff < nums[0]) continue;
if(binarySearch(nums, nums[i] - diff - diff, idx) != -1) {
cnt++;
}
}
return cnt;
}
public int binarySearch(int[] nums, int n, int right){
int L = 0, R = right - 1;
while(L <= R) {
int mid = L + ((R - L) >> 1);
if(nums[mid] == n) {
return mid;
}
if(nums[mid] < n) {
L = mid + 1;
}else{
R = mid - 1;
}
}
return -1;
}
}
|
JavaScript 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| var arithmeticTriplets = function(nums, diff) {
const n = nums.length;
let cnt = 0;
for(let i = 0; i < n; i++) {
let idx = binarySearch(nums, nums[i] - diff, i);
if(idx == -1 || nums[i] - diff - diff < nums[0]) continue;
if(binarySearch(nums, nums[i] - diff - diff, idx) != -1) {
cnt++;
}
}
return cnt;
}
function binarySearch(nums, n, right){
let L = 0, R = right - 1;
while(L <= R) {
const mid = L + ((R - L) >> 1);
if(nums[mid] == n) {
return mid;
}
if(nums[mid] < n) {
L = mid + 1;
}else{
R = mid - 1;
}
}
return -1;
}
|
复杂度分析
- 时间复杂度：$O(n\ log\ n)$ 其中
n 是数组 nums 的长度， 每次二分查找的时间复杂度为 $log\ n$
- 空间复杂度：$O(1)$ 只需要常数的额外空间。