给定一个数组arr，先递减然后递增，返回arr中有多少个绝对值不同的数字？
双指针。左指针最左，符合条件时右移；右指针最右，符合条件时左移。左指针和右指针，谁大谁移动；同样大，都移动。时间复杂度O(N)，额外空间复杂度O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
)
func main() {
arr := []int{-2, -2, -3, -4, -3, -3, -2, -2, 3, 4}
if true {
ret := diff1(arr)
fmt.Println(ret)
}
if true {
ret := diff2(arr)
fmt.Println(ret)
}
}
func diff1(arr []int) int {
set := make(map[int]struct{})
for _, v := range arr {
set[v] = struct{}{}
}
return len(set)
}
// 时间复杂度O(N)，额外空间复杂度O(1)
func diff2(arr []int) int {
N := len(arr)
L := 0
R := N - 1
count := 0
leftVal := 0
rightVal := 0
for L <= R {
count++
leftVal = arr[L]
rightVal = arr[R]
if leftVal < rightVal {
for R >= 0 && arr[R] == rightVal {
R--
}
} else if leftVal > rightVal {
for L < N && arr[L] == leftVal {
L++
}
} else {
for L < N && arr[L] == leftVal {
L++
}
for R >= 0 && arr[R] == rightVal {
R--
}
}
}
return count
}执行结果如下：
