给定一个数组arr，代表每个人的能力值。再给定一个非负数k，如果两个人能力差值正好为k，那么可以凑在一起比赛一局比赛只有两个人，返回最多可以同时有多少场比赛

墨蓝 2024-03-27 09:11 38阅读 0赞

#### 目录 ####

*   *  题目描述
     *  题目解析
     *  代码实现+对数器

### 题目描述 ###

> 给定一个数组arr，代表每个人的能力值。再给定一个非负数k，如果两个人能力差值正好为k，那么可以凑在一起比赛一局比赛只有两个人，返回最多可以同时有多少场比赛  
> 比如： \[3，1，5，7\]，最多同时有2场比赛\[3，1\]；\[5，7\]

### 题目解析 ###

先将数组排序，用窗口。  
举个例子：  
（1）刚开始，L和R均在1位置  
![在这里插入图片描述][fc5ea929cc0044fb9fd8a15e522d4ad7.png]  
（2）L和R能不能比赛？不能，因为它们是一个人，那么R后移

*  必须要区分是不是同一个人，因为k有可能为0

![在这里插入图片描述][ed93e5e7f6824743a7d27eb38c6ad95c.png]  
（3）L和R能不能比赛？看两者差值 = arr\[R\] - arr\[L\]

*  差值 < K，就让R动（差值要变大）
 *  差值 = K，能比赛
 *  差值 > K，就让L动（差值要变小）

这里差值 = 0，不能比赛，R移动一位  
![在这里插入图片描述][194129a32a75429f8eac3f9ebf77f6a8.png]

（3）L和R能不能比赛？看两者差值 = arr\[R\] - arr\[L\]

*  差值 = 2，能比赛

那么ans++，然标记3已经用过了，然后移动L和R  
![在这里插入图片描述][91537c0ee8664b498f086c6b3606f040.png]

![在这里插入图片描述][b0711a06aca84ef38bf229a311d6e98f.png]  
因为2，3已经用过了，所以L++，直到第一个没有用过的位置  
![在这里插入图片描述][3bc694faceba4cbcb5f1e22836111d78.png]  
（4）L和R能不能比赛？不能，因为它们是一个人，那么R后移  
![在这里插入图片描述][482593ea7fc84322add50f9484540946.png]  
（5）L和R能不能比赛？能  
![在这里插入图片描述][98f9f914845e4680b60831de1fb2c671.png]  
![在这里插入图片描述][c7b62cca22cc4732b92b1f01b8b6e906.png]  
（6）R已经超出范围，所以结束

### 代码实现+对数器 ###

public class MaxPairNumber {
        
    
        // 暴力解
        public static int maxPairNum1(int[] arr, int k) {
        
            if (k < 0) {
        
                return -1;
            }
            return process1(arr, 0, k);
        }
    
        public static int process1(int[] arr, int index, int k) {
        
            int ans = 0;
            if (index == arr.length) {
        
                for (int i = 1; i < arr.length; i += 2) {
        
                    if (arr[i] - arr[i - 1] == k) {
        
                        ans++;
                    }
                }
            } else {
        
                for (int r = index; r < arr.length; r++) {
        
                    swap(arr, index, r);
                    ans = Math.max(ans, process1(arr, index + 1, k));
                    swap(arr, index, r);
                }
            }
            return ans;
        }
    
        public static void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    
        // 时间复杂度O(N*logN)
        public static int maxPairNum2(int[] arr, int k) {
        
            if (k < 0 || arr == null || arr.length < 2) {
        
                return 0;
            }
            Arrays.sort(arr);
            int ans = 0;
            int N = arr.length;
            int L = 0;
            int R = 0;
            boolean[] usedR = new boolean[N];
            while (L < N && R < N) {
        
                if (usedR[L]) {
          //L跳过已经用过的位置
                    L++;
                } else if (L == R) {
          // 窗口同一个人时，R++扩大窗口
                    R++;
                } else {
         // 不止一个数，而且都没用过！
                    int distance = arr[R] - arr[L];
                    if (distance == k) {
        
                        ans++;
                        usedR[R++] = true;
                        L++;
                    } else if (distance < k) {
        
                        R++;
                    } else {
        
                        L++;
                    }
                }
            }
            return ans;
        }
    
        // 为了测试
        public static int[] randomArray(int len, int value) {
        
            int[] arr = new int[len];
            for (int i = 0; i < arr.length; i++) {
        
                arr[i] = (int) (Math.random() * value);
            }
            return arr;
        }
    
        // 为了测试
        public static void printArray(int[] arr) {
        
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // 为了测试
        public static int[] copyArray(int[] arr) {
        
            int[] ans = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
        
                ans[i] = arr[i];
            }
            return ans;
        }
    
        public static void main(String[] args) {
        
            int maxLen = 10;
            int maxValue = 20;
            int maxK = 5;
            int testTime = 1000;
            System.out.println("功能测试开始");
            for (int i = 0; i < testTime; i++) {
        
                int N = (int) (Math.random() * (maxLen + 1));
                int[] arr = randomArray(N, maxValue);
                int[] arr1 = copyArray(arr);
                int[] arr2 = copyArray(arr);
                int k = (int) (Math.random() * (maxK + 1));
                int ans1 = maxPairNum1(arr1, k);
                int ans2 = maxPairNum2(arr2, k);
                if (ans1 != ans2) {
        
                    System.out.println("Oops!");
                    printArray(arr);
                    System.out.println(k);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    break;
                }
            }
            System.out.println("功能测试结束");
        }
    
    }

[fc5ea929cc0044fb9fd8a15e522d4ad7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ed792f6cc57443678fbe9eda84b95f6d.png
[ed93e5e7f6824743a7d27eb38c6ad95c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bc80e725e4a543aca8a2e82d84d5964a.png
[194129a32a75429f8eac3f9ebf77f6a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a421b5b50ed14b43a981c62707e8ad9e.png
[91537c0ee8664b498f086c6b3606f040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2b140dd9255d42eb82cab9870739129c.png
[b0711a06aca84ef38bf229a311d6e98f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b481a059357646d7a7815c5f194d7c56.png
[3bc694faceba4cbcb5f1e22836111d78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0f6990265a154106bb293770f32c79e4.png
[482593ea7fc84322add50f9484540946.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8c3168117f124950812b64e709bc8df3.png
[98f9f914845e4680b60831de1fb2c671.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d7576875b5984e148f13fb5c35a6b131.png
[c7b62cca22cc4732b92b1f01b8b6e906.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/03a7fb4e40ec42c1b44fa353aa4861e5.png