2021-06-23：给定一个数组arr，代表每个人的能力值。再给定一个非负数k

原创

福大大架构师每日一题

修改于 2021-06-24 02:12:56

9490

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

福大大答案2021-06-23：

时间紧，思路见代码。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8}
    ret := maxPairNum2(arr, 2)
    fmt.Println(ret)
}

// 时间复杂度O(N*logN)
func maxPairNum2(arr []int, k int) int {
    if k < 0 || len(arr) < 2 {
        return 0
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] <= arr[j]
    })
    ans := 0
    N := len(arr)
    L := 0
    R := 0
    usedR := make([]bool, N)

    for L < N && R < N {
        if usedR[L] {
            L++
        } else if L >= R {
            R++
        } else { // 不止一个数，而且都没用过！
            distance := arr[R] - arr[L]
            if distance == k {
                ans++
                usedR[R] = true
                R++
                L++
            } else if distance < k {
                R++
            } else {
                L++
            }
        }
    }
    return ans
}