找到一个数组里面相加等于给定值的元素
最简单的for循环迭代 每个元素相加
由于 findAllTwoSum 函数是在主循环中被调用的，所以总体时间复杂度为 O(n * (n-i))，其中 i 的取值范围是 0 到 n-1。在最坏的情况下，这个时间复杂度可能接近 O(n^2)。
package main
import (
"fmt"
)
const (
target = 8
)
func findAllTwoSum(arr []int64, index int, ele int64) {
for i := 0 ; i < len(arr); i++ {
if i <= index {
continue
}
if target == (arr[i] + ele) {
fmt.Println(ele, arr[i])
}
}
}
func findAllTwoSum() {
arr := []int64{1,2,3,4,5,6,7,8,12,45,8,-1,-2,-3,-4}
for i, ele := range arr {
add(arr, i, ele)
}
}
map 计算 整体时间复杂度为 O(n)
package main
import (
"fmt"
)
func findAllTwoSum(arr []int, target int) [][]int {
numIndex := map[int]int{}
result := [][]int{}
for i, v := range arr {
// A B C 迭代C，需要A 记录 A C
current := target - v
if idx, ok := numIndex[current]; ok {
result = append(result, []int{arr[idx], v})
}
numIndex[v] = i
}
return result
}
func main() {
arr := []int{1, 2, 3, 4, 5, 6, 7, -16, 24, 9, -1, -2, -3, -4, -5, -6, -7, -9}
target := 8
r := findAllTwoSum(arr, target)
for _, v := range r {
fmt.Printf("%d + %d = %d\n", v[0], v[1], target)
}
}
双指针运算 排序的时间复杂度为 O(n log n)，因此主要的时间复杂度来自排序。因此，总体的时间复杂度为 O(n log n)
package main
import (
"fmt"
"sort"
)
type AddData struct {
A, B int
}
func findAllTwoSum(arr []int, target int) []AddData {
sort.Ints(arr)
i, n := 0, len(arr)-1
result := []AddData{}
for i < n {
// 先算出目标值
current := arr[i] + arr[n]
if target == current {
result = append(result, AddData{
A: arr[i],
B: arr[n],
})
i += 1
n -= 1
// 右移指针
} else if current < target {
i += 1
} else {
n -= 1
}
}
return result
}
func main() {
arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 37, 12, 44, 45, 8, -1, -2, -3, -4}
target := 45
r := findAllTwoSum(arr, target)
for _, v := range r {
fmt.Printf("%d + %d = %d\n", v.A, v.B, target)
}
}