算术三元组的数目【LC2367】
给你一个下标从 0 开始、严格递增 的整数数组
nums和一个正整数diff。如果满足下述全部条件，则三元组(i, j, k)就是一个 算术三元组 ：
i < j < k，nums[j] - nums[i] == diff且nums[k] - nums[j] == diff返回不同 算术三元组 的数目*。*
枚举+二分查找
- 思路：枚举+二分查找
class Solution { public int arithmeticTriplets(int[] nums, int diff) { int res = 0; for (int i = 0; i < nums.length; i++){ if (binarySearch(nums, nums[i] + diff) != -1 && binarySearch(nums, nums[i] + 2 * diff) != -1){ res++; } } return res; } public int binarySearch(int[] nums, int target){ int l = 0, r = nums.length - 1; while (l <= r){ int mid = (l + r) >> 1; if (nums[mid] == target){ return mid; }else if (nums[mid] > target){ r = mid - 1; }else{ l = mid + 1; } } return -1; } }
class Solution { public int arithmeticTriplets(int[] nums, int diff) { Set<Integer> set = new HashSet<>(); int res = 0; for (int i = 0; i < nums.length; i++){ if (set.contains(nums[i] - diff) && set.contains(nums[i] - 2 * diff)){ res++; } set.add(nums[i]); } return res; } }
