Golang 使用双指针方法在给定数组中查找给定子数组

在这篇Golang文章中，我们将使用迭代和优化迭代方法，使用双指针方法来查找给定数组中是否存在给定的子数组。数组是一组具有相同数据类型的元素，按照连续的内存块排列，并使用索引或下标进行访问。

语法

func isSubarrayPresent(arr []int, sub []int) bool {…}

isSubarrayPresent()函数使用双指针方法在给定数组中查找给定子数组是否存在。它以数组和子数组作为参数。

步骤

步骤 1 - 首先，我们需要导入fmt包。
步骤 2 - 现在，创建一个isSubarrayPresent()函数，它接受一个整数类型的数组和子数组。这个函数将返回一个布尔值，指示子数组是否存在于数组中。
步骤 3 - 例如 1 – 如果子数组的长度为零，那么说明它是空的，并且存在于任何数组中。因此，在这种情况下返回true。否则，使用for循环使用一定的条件来匹配子数组的元素和数组。如果子数组的所有元素都存在于数组中，则返回true，否则返回false。

例如 2 – 首先检查子数组的长度是否大于数组的长度，如果是，则返回false。否则，使用for循环加上if-else条件来匹配子数组的元素和数组。如果有匹配，函数会将j增加到下一个子数组元素。如果没有匹配，函数将j重置为零，并将i增加到下一个数组元素。如果子数组的所有元素都存在于数组中，则返回true，否则返回false。

步骤 4 - 开始main()函数。在main()函数内部，初始化数组和子数组。
步骤 5 - 现在，调用isSubarrayPresent()函数，并将数组和子数组传递给它。
步骤 6 - 进一步使用fmt.Println()函数打印结果布尔值。

示例1

在这个示例中，我们将使用迭代方法定义一个isSubarrayPresent()函数，该函数使用双指针方法在给定数组中查找给定子数组是否存在。

package main

import "fmt"

func isSubarrayPresent(arr []int, sub []int) bool {
   if len(sub) == 0 {
      return true
   }

   i := 0
   j := 0

   for i < len(arr) {
      if arr[i] == sub[j] {
         j++
         if j == len(sub) {
            return true
         }
      } else {
         i -= j
         j = 0
      }
      i++
   }
   return false
}

func main() {
   arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
   sub1 := []int{2, 3, 4}
   sub2 := []int{4, 3, 2}
   sub3 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

   fmt.Println(isSubarrayPresent(arr, sub1)) 
   fmt.Println(isSubarrayPresent(arr, sub2)) 
   fmt.Println(isSubarrayPresent(arr, sub3)) 
}

输出

true
false
false

示例2

在这个示例中，我们将定义一个isSubarrayPresent()函数，使用迭代的方式来优化它，用于使用双指针方法在给定数组中查找给定子数组是否存在。

package main

import "fmt"

func isSubarrayPresent(arr []int, sub []int) bool {
   n := len(arr)
   m := len(sub)

   if m > n {
      return false
   }

   i := 0
   j := 0

   for i < n && j < m {
      if arr[i] == sub[j] {
         j++
      } else if j > 0 && arr[i] == sub[j-1] {
         j--
         continue
      } else {
         i = i - j
         j = 0
      }
      i++
   }
   return j == m
}

func main() {
   arr := []int{10, 20, 30, 40, 50, 60, 70, 80, 90}
   s1 := []int{40, 50, 9}
   s2 := []int{5, 2, 10}
   s3 := []int{10, 20, 30, 40, 50}
   fmt.Println(isSubarrayPresent(arr, s1))
   fmt.Println(isSubarrayPresent(arr, s2))
   fmt.Println(isSubarrayPresent(arr, s3))
}