使用双指针方法在给定数组中查找给定子数组是否存在的Golang程序

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

语法

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

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

算法

步骤1 -首先，我们需要导入fmt包。
步骤2 -现在，创建一个isSubarrayPresent()函数，它需要一个整数类型的数组和一个子数组作为参数。该函数将返回一个布尔值，指示是否在数组中存在子数组。
步骤3 -

如果子数组的长度为零，那么它为空并且存在于任何数组中，因此在这种情况下返回true。否则，使用for循环使用特定条件将子数组的元素与数组的元素进行匹配。如果子数组的所有元素都存在于数组中，则返回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))
}