使用双指针方法查找两个已排序数组交集的 Go 语言程序

---

在这篇 Go 语言文章中，我们将编写程序，使用双指针方法查找两个数组的交集。交集表示相似性或最常见的部分，两个数组的交集指的是两个数组之间相同的元素。

语法

func make ([] type, size, capacity)

Go 语言中的 make 函数用于创建数组/映射，它接受要创建的变量类型、大小和容量作为参数。

func append(slice, element_1, element_2…, element_N) []T

append 函数用于向数组切片添加值。它接受多个参数。第一个参数是要添加值的数组，后面跟着要添加的值。然后，该函数返回包含所有值的最终数组切片。

func range(variable)

range 函数用于迭代任何数据类型。要使用它，我们首先必须编写 range 关键字，后面跟着要迭代的数据类型，结果循环将迭代到变量的最后一个元素。

sort.Ints()

此函数属于 sort 包，用于对包含整数值的切片/数组进行排序。

在 if-else 条件语句中使用双指针方法

在这种方法中，我们将编写一个 Go 语言程序，使用 if 条件语句查找两个数组的交集，该条件语句用于比较数组元素并将交集点添加到切片中以打印输出。

算法

• 步骤 1 - 在程序中导入 fmt、main 和 sort 包，其中 fmt 帮助格式化输入和输出，main 确保程序应为可执行程序，sort 用于对数组进行排序。

• 步骤 2 - 创建一个名为 intersect 的函数，该函数有两个输入参数 array1 和 array2。

• 步骤 3 - 使用 sort 包中的 Ints 方法对两个数组进行排序。

• 步骤 4 - 然后，将变量 i 和 j 初始化为 0，这些变量指的是数组的索引。

• 步骤 5 - 在此步骤中，创建一个空的交集切片来存储两个数组的交集点。

• 步骤 6 - 遍历 array1 和 array2，并检查元素是否相同，将元素追加到交集切片中，并增加 i 和 j 变量。

• 步骤 7 - 如果第一个数组元素小于第二个数组元素，则增加 I 变量，否则增加 j 变量。

• 步骤 8 - 最后，将切片返回到创建的外部函数，在 main 函数中，将接收输出并使用 fmt 包中的 Println 函数打印到控制台，其中 ln 表示换行。

示例

以下 Go 语言程序说明了如何在 if-else 条件语句中使用双指针方法查找两个数组的交集。

package main

import (
   "fmt"
   "sort"
)

func intersect(array1 []int, array2 []int) []int {
	
   sort.Ints(array1)
   sort.Ints(array2)
	
   i := 0 
   j := 0 

   var intersection []int
	
   for i < len(array1) && j < len(array2) {
      // If the elements are the same, add it to the intersection slice
      if array1[i] == array2[j] {
         intersection = append(intersection, array1[i])
         i++
         j++
      } else if array1[i] < array2[j] {
         i++
      } else {
         j++
      }
   }
   return intersection
}
func main() {
	
   array1 := []int{1, 2, 2, 3}
   array2 := []int{2, 2}

   intersection_points := intersect(array1, array2)

   fmt.Println("The intersection points of the two arrays are:")
   fmt.Println(intersection_points) 
}

输出

The intersection points of the two arrays are:
[2 2]

在频率映射中使用双指针方法

在这种方法中，我们将编写一个 Go 语言程序，使用频率映射查找两个数组的交集，该映射将用于计算每个元素出现的次数并将结果存储在映射中。

算法

• 步骤 1 - 在程序中导入 fmt 和 main 包，其中 fmt 帮助格式化输入和输出，main 确保程序应为可执行程序。

• 步骤 2 - 创建一个名为 intersect 的函数，该函数有两个输入 array1 和 array2，并在该函数中使用 make 函数（Go 中的内置函数）创建一个频率映射。

• 步骤 3 - 迭代 array1 并计算数组中元素出现的次数，并将结果存储在映射中。

• 步骤 4 - 在此步骤中，创建一个交集切片来存储两个数组的交集点。

• 步骤 5 - 接下来，迭代 array2 并检查元素的频率是否大于 0。

• 步骤 6 - 如果条件满足，则将值追加到交集切片中，并减少该值。

• 步骤 7 - 将切片返回到外部函数，并在 main 函数中使用 fmt 包中的 Println 函数打印输出，其中 ln 表示换行。

示例

以下 Go 语言程序说明了如何在频率映射中使用双指针方法查找两个数组的交集。

package main

import "fmt"

func intersect(array1 []int, array2 []int) []int {
	 
   freq := make(map[int]int)
   for _, value := range array1 {
      freq[value]++    
   }
	
   var intersection []int
	
   for _, value := range array2 {
      if freq[value] > 0 {
         intersection = append(intersection, value)
         freq[value]--
      }
   }
   return intersection
}

func main() {
   array1 := []int{1, 2, 2, 3}
   array2 := []int{2, 2}
   intersection_point := intersect(array1, array2)
   fmt.Println("The intersection point of two arrays is:")
   fmt.Println(intersection_point) 
}

输出

The intersection point of two arrays is:
[2 2]

结论

我们使用两个示例编译并执行了使用双指针方法查找两个数组交集的程序。在第一个示例中，我们使用了条件 if-else 语句，在第二个示例中，我们使用了频率映射来获取输出。