Array篇easy难度之不等式多项式变换

题目描述

https://leetcode.com/problems/count-good-triplets/submissions/

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.
A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x| denotes the absolute value of x.
Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].
Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.
 

Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

博主提交的代码

时间复杂度(O^3)，空间复杂度O(1)

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int result = 0;
        for( int i = 0; i < arr.length; i++){
            for(int j = i+1; j < arr.length; j++){
                for(int k = j + 1; k < arr.length; k++){
                    if(
                        (abs(arr[i] - arr[j]) <= a) && 
                        (abs(arr[j] - arr[k]) <= b) &&
                        (abs(arr[i] - arr[k]) <= c)
                    ){
                        result++;
                    }
                }
            }
        }
        return result;
    }
    public int abs(int input){
        if(input < 0){
            return -input;
        }else{
            return input;
        }
    }
}

他人的解法

python实现 O(n^2)，但是空间复杂度O(n)

这段代码的原理是根据题干里面的不等式
|arr[i] - arr[j]| <= a (不等式1)
|arr[j] - arr[k]| <= b (不等式2)
|arr[i] - arr[k]| <= c (不等式3)
第一个循环是直观基于不等式1的，对于第二个循环
对于不等式2,把绝对值符号拆开后，对于arr[j] - arr[k]大于0和小于0 的分为两个不等式
|arr[j] - arr[k]| <= b 等价于
arr[j] - arr[k] <= b (arr[i] - arr[j] >0)
arr[k] - arr[j] <= b (arr[j] - arr[i] <=0)
然后将打开绝对值的不等式变化后
arr[k] >= arr[j] - b (arr[i] - arr[j] >0)
arr[k] <= arr[j] + b (arr[j] - arr[i] <=0)
同理，将不等式3变化后，将得到下面的不等式
arr[k] >= arr[i] - c (arr[i] - arr[k] > 0)
arr[k] <= arr[i] + c (arr[i] - arr[k] <= 0)
那么会有人问，为什么我们对于不等式2和3要这么变化，其实原因是我们在第一个循环之后，只能知道arr[i] ,a,b,c这几个值，所以要将他们提前存储好，用于后续的逻辑判断

def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
    count = 0
    length = len(arr)
    potential = []
    # double for loops is O(n^2) in the worst case; n = len(arr)
    for i in range(length):
        for j in range(i+1, length):
            if abs(arr[i] - arr[j]) <= a:
                # storing the j index to iterate on (j < k), and the bounds to compare
                # from our absolute values + inequalities since we have to ensure
                # that k is within range 
                # ex. | a[j] - a[k] | <= b  ---> -b <= arr[j] - arr[k] <= b
                potential.append([j, b + arr[j], - b + arr[j], c + arr[i], - c + arr[i]])
    
    # O(n^2) since p is at most length n and we're iterating on k
    for p in potential:
        for k in range(p[0]+1, length):
            if p[1]>=arr[k]>=p[2] and p[3]>=arr[k]>=p[4]:
                count += 1
    return count

java复刻

不过在leetcode上运行了过后，运行速度变慢了，看来空间也没有换到多少时间

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int result = 0;
        List<Map<String,Integer>> cache = new ArrayList<>();
        for( int i = 0; i < arr.length; i++){
            for( int j = i+ 1; j < arr.length; j ++){
                if( abs( arr[i] - arr[j]) <= a){
                    Map<String, Integer> eachCache = new HashMap<String,Integer>(); 
                    eachCache.put("j-b", arr[j] - b);
                    eachCache.put("j+b", arr[j] + b);
                    eachCache.put("i-c", arr[i] - c);
                    eachCache.put("i+c", arr[i] + c);
                    eachCache.put("j", j);
                    cache.add(eachCache);
                }
            }
        }
        for(Map<String, Integer> eachCache: cache){
            int v1 = eachCache.get("j-b");
            int v2 = eachCache.get("j+b");
            int v3 = eachCache.get("i-c");
            int v4 = eachCache.get("i+c");
            int j = eachCache.get("j");
            for(int k = j + 1; k < arr.length; k++){
                if( arr[k] >= v1 && arr[k] <= v2 && arr[k] >= v3 && arr[k] <= v4){
                    result++;
                }
            }
            
        }
            
        return result;
    }
    public int abs(int input){
        if(input < 0){
            return -input;
        }else{
            return input;
        }
    }
    
}