马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
问题背景
给你一个整数数组 a r r arr arr，以及 a 、 b 、 c a、b 、c a、b、c 三个整数。请你统计其中好三元组的数目。
假如三元组 ( a r r [ i ] , a r r [ j ] , a r r [ k ] ) (arr, arr[j], arr[k]) (arr,arr[j],arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。
- 0 ≤ i < j < k < a r r . l e n g t h 0 \le i < j < k < arr.length 0≤i<j<k<arr.length
- ∣ a r r [ i ] − a r r [ j ] ∣ ≤ a |arr - arr[j]| \le a ∣arr−arr[j]∣≤a
- ∣ a r r [ j ] − a r r [ k ] ∣ ≤ b |arr[j] - arr[k]| \le b ∣arr[j]−arr[k]∣≤b
- ∣ a r r [ i ] − a r r [ k ] ∣ ≤ c |arr - arr[k]| \le c ∣arr−arr[k]∣≤c
其中 ∣ x ∣ |x| ∣x∣ 表示 x x x 的绝对值。
返回 好三元组的数目 。
数据约束
- 3 ≤ a r r . l e n g t h ≤ 100 3 \le arr.length \le 100 3≤arr.length≤100
- 0 ≤ a r r [ i ] ≤ 1000 0 \le arr \le 1000 0≤arr≤1000
- 0 ≤ a , b , c ≤ 1000 0 \le a, b, c \le 1000 0≤a,b,c≤1000
解题过程
题中要求的约束有三个，暴力枚举的时间复杂度是 O ( N 3 ) O(N ^ 3) O(N3)。
假如数组是有序的，那可以很轻易地进步时间方面的效率，但是结果与元素的初始位置有关，以是不方便直接排序。
退而求其次，定义一个下标数组，对它进行排序。
然后将数组中的元素当作 j j j 来遍历，将满足 ∣ a r r [ i ] − a r r [ j ] ∣ ≤ a |arr - arr[j]| \le a ∣arr−arr[j]∣≤a 以及 ∣ a r r [ j ] − a r r [ k ] ∣ ≤ b |arr[j] - arr[k]| \le b ∣arr[j]−arr[k]∣≤b
两个条件的原数组中的元素分别记录到哈希表中。
接下来只要再求满足第三个条件的元素对的数目，根据绝对值的定义，可以在线性的时间内得到合法结果的上下限。
具体实现
- class Solution {
- public int countGoodTriplets(int[] arr, int a, int b, int c) {
- Integer[] idx = new Integer[arr.length];
- Arrays.setAll(idx, i -> i);
- Arrays.sort(idx, (i, j) -> arr[i] - arr[j]);
- int res = 0;
- for (int j : idx) {
- int cur = arr[j];
- List<Integer> list1 = new ArrayList<>();
- for (int i : idx) {
- if (i < j && Math.abs(arr[i] - cur) <= a) {
- list1.add(arr[i]);
- }
- }
- List<Integer> list2 = new ArrayList<>();
- for (int k : idx) {
- if (k > j && Math.abs(arr[k] - cur) <= b) {
- list2.add(arr[k]);
- }
- }
- int left = 0;
- int right = 0;
- for (int item : list1) {
- while (right < list2.size() && list2.get(right) <= item + c) {
- right++;
- }
- while (left < list2.size() && list2.get(left) < item - c) {
- left++;
- }
- res += right - left;
- }
- }
- return res;
- }
- }
|
