There is a repeating element iii[pruning with ordered ordering]

Preface

When the time complexity is O(NlongN || N²) when , Without special requirements , Sequencing has no effect on time complexity , You can even prune with the order after the order is arranged , Reduce running time .
Not just DFS Can prune , There are many pruning ideas in many operations .

One 、 There are duplicate elements III

Two 、 Sort + prune

package everyday.medium;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

//  There are duplicate elements III
public class ContainsNearbyAlmostDuplicate {
    
    /* target： The limited range of a given subscript , Limited range of element difference , Ask whether there is such   Number pair . */
    //  violence 
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        int n = nums.length;
        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                if (Math.abs((long) i - j) <= k
                        && Math.abs((long) nums[i] - nums[j]) <= t)
                    return true;
            }
        }
        return false;
    }
}

//  Nonviolence , Ingenious explanation ： Prioritize , Then prune by order .（ notes ： Anyway, for O(NlogN || N2) Time complexity of , Put it in order completely for every effect .）
class ContainsNearbyAlmostDuplicate2 {
    
    /* target： The limited range of a given subscript , Limited range of element difference , Ask whether there is such   Number pair . */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        List<int[]> arr = new ArrayList<>();
        int idx = 0;
        for (int num : nums) arr.add(new int[]{
    idx++, num});
        arr.sort(Comparator.comparingInt(o -> o[1]));
        //  Explosive search  +  prune 
        for (int i = 0; i < arr.size() - 1; i++) {
    
            //  notes : Actually  j = i + 1 Even if the first pruning .
            for (int j = i + 1; j < arr.size(); j++) {
    
                int[] a = arr.get(i), b = arr.get(j);

                if (Math.abs((long) a[1] - b[1]) <= t
                        && Math.abs((long) a[0] - b[0]) <= k) return true;
                //  Similar to pruning .
                if (Math.abs((long) a[1] - b[1]) > t) break;
            }
        }
        return false;
    }

}

summary

1） Pruning ideas exist in many operations , not only DFS.
2） When to use sorting boldly ？ Order is a good condition .

reference

[1] LeetCode There are duplicate elements III