前言
题目来自LeetCode：2367.算术三元组的数目
题目（难度：简单）（解法层层优化）
给你一个下标从 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 。
提示：
- 3 <= nums.length <= 200
- 0 <= nums[i] <= 200
- 1 <= diff <= 50
- nums 严格 递增
题解
这题看起开就是暴力解决问题，因为数据量小。思考时间复杂度更低的算法能预防以后同样类型题目数据量大的情况。
枚举 O(n^3)(n < 10^3可使用)
枚举，也就是暴力，没什么可说的，直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int arithmeticTriplets(int[] nums, int diff) {
int len = nums.length;
int res = 0;
for(int i = 0; i < len - 2; i++){
for(int j = i + 1; j < len - 1; j++){
if(nums[j] - nums[i] == diff){
for(int k = j + 1; k < len; k++){
if(nums[k] - nums[j] == diff){
res++;
}
}
}
}
}
return res;
}
}
|
二分查找 O(nlognlogn)(大约是n < 10^5可使用)
在枚举的基础上优化，因为数组是严格递增的，所以可以使用两次二分，第一次寻找diff + nums[i], 即nums[j], 如果找到，继续使用二分找diff + nums[j],即nums[k]。
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
30
31
32
33
34
35
36
| class Solution {
public int arithmeticTriplets(int[] nums, int diff) {
int len = nums.length;
int res = 0;
for(int i = 0; i < len; i++){
int j = binarySearch(nums, i + 1, len - 1, diff + nums[i]);
if(j != -1){
int k = binarySearch(nums, j + 1, len - 1, diff + nums[j]);
if(k != -1){
res++;
}
}
}
return res;
}
public int binarySearch(int[] nums, int l, int r, int key){
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] > key){
r = mid - 1;
}else if(nums[mid] < key){
l = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
|
哈希表O(n) (n < 10^9可使用)
典型的用空间换时间，需要额外空间O(n)。i，j，k要满足nums[j] - nums[i] = diff, nums[k] - nums[j] = diff, 整理一下，nums[j] = nums[i] + diff, nums[k] = nums[i] + 2 * diff。但还需要满足i < j < k, 又因为数组是严格递增的且diff > 0，所以在满足等式成立的情况下，i < j < k恒成立。即本题i < j < k这个条件可以忽略，也就是和顺序无关。那么，可以把数组全部存到哈希表中，遍历数组，对于每个nums[i]，在哈希表中查找是否存在nums[i] + diff和nums[i] + 2 * diff即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int arithmeticTriplets(int[] nums, int diff) {
HashSet<Integer> hs = new HashSet<>();
int len = nums.length;
int res = 0;
for(int i = 0; i < len; i++){
hs.add(nums[i]);
}
for(int i = 0; i < len; i++){
if(hs.contains(nums[i] + diff) && hs.contains(nums[i] + 2 * diff)){
res++;
}
}
return res;
}
}
|
三指针O(n) (n < 10^9可使用)
三指针能在不需要额外空间的情况下做到O(n)。维护三个指针i，j，k，当找到第一个三元组时，下一个成立的三元组i1，j1，k1，必有i1 > i, j1 > j, k1 > k。那么只需要让他们一直往右遍历即可。
需要注意的时边界的判断，i < n - 2, j < n - 1, k < n。
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 len = nums.length;
int res = 0;
for(int i = 0, j = 1, k = 2; i < len - 2 && j < len - 1 && k < len; i++){
j = Math.max(j, i + 1);
while(j < len - 1 && nums[j] - nums[i] < diff){
j++;
}
if(j < n - 1 && nums[j] - nums[i] == diff){
k = Math.max(k, j + 1);
while(k < len && nums[k] - nums[j] < diff){
k++;
}
if(k < len && nums[k] - nums[j] == diff){
res++;
}
}
}
return res;
}
}
|