给你一个下标从 0 开始、严格递增的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个算术三元组：
- i < j < k ，
nums[j] - nums[i] == diff且nums[k] - nums[j] == diff
返回不同 算术三元组 的数目。
# 解题思路
整体思路是枚举，不过本题条件很多，比如数组是严格递增的，数组长度、数组的每个元素的数值较小，所以有三种方法进行求解：
- 直接枚举每个元素，进行判断
使用哈希表进行优化，即每次枚举最小的数 nums[i] ，那么就只需要判断 nums[i] + diff 与 nums[i] + 2 * diff 是否存在即可，故有以下两种优化方法：
2. 使用 hashset
3. 使用 boolean 数组
# 法一：直接暴力
class Solution { | |
public int arithmeticTriplets(int[] nums, int diff) { | |
int ans = 0; | |
int n = nums.length; | |
for (int i = 0; i < n - 2; ++i) { | |
for (int j = i + 1; j < n - 1; ++j) { | |
if (nums[j] - nums[i] == diff) { | |
for (int k = j + 1; k < n; ++k) { | |
if (nums[k] - nums[j] == diff) | |
++ans; | |
} | |
} | |
} | |
} | |
return ans; | |
} | |
} |
提交结果：
# 法二：hashset
class Solution { | |
public int arithmeticTriplets(int[] nums, int diff) { | |
int ans = 0; | |
int n = nums.length; | |
// 建立哈希表，便于快速查找某个数是否存在 | |
Set<Integer> set = new HashSet<>(); | |
for (int num : nums) set.add(num); | |
//nums 严格递增，所以 nums [i]+diff, nums [i]+2*diff 出现在当前位置之后 | |
for (int i = 0; i < n - 2; ++i) { | |
if (set.contains(nums[i] + diff) && set.contains(nums[i] + 2 * diff)) { | |
++ans; | |
} | |
} | |
return ans; | |
} | |
} |
提交结果：
# 法三：数组模拟哈希表
class Solution { | |
public int arithmeticTriplets(int[] nums, int diff) { | |
int ans = 0; | |
int n = nums.length; | |
// 数组模拟哈希表，便于快速查找某个数是否存在 | |
boolean[] hash = new boolean[201]; | |
for (int num : nums) hash[num] = true; | |
//nums 严格递增，所以 nums [i]+diff, nums [i]+2*diff 出现在当前位置之后 | |
for (int i = 0; i < n - 2; ++i) { | |
int x = nums[i] + 2 * diff; | |
// 数组严格递增，如果大于了数据范围，直接跳出循环 | |
if (x >= hash.length) break; | |
// 如果 nums [i]+x 和 nums [i]+2*diff 都存在，结果 + 1 | |
if (hash[x - diff] && hash[x]) { | |
++ans; | |
} | |
} | |
return ans; | |
} | |
} |
提交结果：
