使用双指针法查找给定和的最长子数组的 Golang 程序

在这篇 Go 语言文章中，我们将使用迭代和优化迭代方法，通过双指针法来查找给定和的最长子数组。数组是由相同数据类型元素组成的集合，这些元素排列在内存的连续块中，并且可以使用索引或下标进行访问。

使用迭代方法的双指针法

在这种方法中，我们将使用迭代方法定义一个 longestSubarray() 函数，该函数用于使用双指针法查找给定和的最长子数组。

算法

  • 步骤 1 − 首先，我们需要导入 fmt 包。

  • 步骤 2 − 启动 main() 函数。在 main() 函数内部，初始化一个数组并提供整数和值。

  • 步骤 3 − 现在，调用 longestSubarray() 函数并将数组和和作为参数传递给它。

  • 步骤 4 − 此外，使用 fmt.Println() 函数打印结果的最长子数组值。

  • 步骤 5 − 现在，创建一个 longestSubarray() 函数，该函数以整数数组和一个和值作为输入。此函数将返回具有给定和的最长子数组。

  • 步骤 6 − 在 longestSubarray() 函数中，检查数组的长度。如果它为 0，则函数返回 nil。

  • 步骤 7 − 该函数使用从 0 开始的索引 end 循环遍历数组的每个元素。在每次迭代中，arr[end] 的值都会添加到 currSum 中。

  • 步骤 8 − 最终，在比较之后，返回具有给定和的结果最长子数组。

示例

以下是使用迭代方法的双指针法查找给定和的最长子数组的 Go 语言程序

package main

import "fmt"

func main() {
   arr := []int{10, 50, 20, 70, 10, 90}
   sum := 90
   subarr := longestSubarray(arr, sum)
   fmt.Println("Longest subarray with the sum of", sum, "is", subarr)
}

func longestSubarray(arr []int, sum int) []int {
   n := len(arr)
   if n == 0 {
      return nil
   }

   maxLen := 0
   maxStart, maxEnd := -1, -1
   currSum, start := 0, 0

   for end := 0; end < n; end++ {
      currSum += arr[end]

      for currSum > sum && start <= end {
         currSum -= arr[start]
         start++
      }

      if currSum == sum && end-start+1 > maxLen {
         maxLen = end - start + 1
         maxStart, maxEnd = start, end
      }
   }

   if maxStart == -1 {
      return nil
   }
   return arr[maxStart : maxEnd+1]
}

输出

Longest subarray with the sum of 90 is [20 70]

使用优化迭代方法的双指针法

在此示例中，我们将使用优化迭代方法定义一个 longestSubarrayWithGivenSum() 函数，该函数用于使用双指针法查找给定和的最长子数组。

算法

  • 步骤 1 − 首先，我们需要导入 fmt 包。

  • 步骤 2 − 首先，创建一个 longestSubarrayWithGivenSum() 函数，该函数以整数数组和目标和值作为输入。此函数将返回具有给定和的最长子数组。

  • 步骤 3 − 该函数使用两个指针 left 和 right 来跟踪起始和结束索引。

  • 步骤 4 − 它将右指针向右移动，同时将每个元素添加到 currentSum 中。如果 currentSum 大于 targetSum，则该函数将左指针向右移动，并从 currentSum 中减去每个元素，直到 currentSum 小于或等于 targetSum。

  • 步骤 5 − 最终，在比较之后，返回具有给定和的结果最长子数组。

  • 步骤 6 − 启动 main() 函数。在 main() 函数内部，初始化一个数组并提供整数目标和值。

  • 步骤 7 − 现在，调用 longestSubarray() 函数并将数组和和作为参数传递给它。

  • 步骤 8 − 然后，如果存在，它将打印具有给定和的最长子数组，或者打印一条消息，指示不存在具有给定和的子数组。

示例

以下是使用优化迭代方法的双指针法查找给定和的最长子数组的 Go 语言程序

package main

import "fmt"

func longestSubarrayWithGivenSum(arr []int, targetSum int) []int {
   var result []int
   var left, right, currentSum int

   for right < len(arr) {
      currentSum += arr[right]

      for currentSum > targetSum {
         currentSum -= arr[left]
         left++
      }

      if currentSum == targetSum && (result == nil || len(result) < right-left+1) {
         result = arr[left : right+1]
      }
      right++
   }
   return result
}

func main() {
   arr := []int{10, 40, 20, 30, 10, 50}
   targetSum := 70

   longestSubarray := longestSubarrayWithGivenSum(arr, targetSum)

   if longestSubarray == nil {
      fmt.Println("No subarray found with the given sum")
   } else {
      fmt.Println("Longest subarray with the given sum:", longestSubarray)
   }
}

输出

Longest subarray with the given sum: [10 40 20]

结论

我们已经成功编译并执行了一个 Go 语言程序，该程序使用迭代和优化迭代方法的双指针法查找给定和的最长子数组，以及两个示例。在第一个示例中，我们使用了迭代方法，在第二个示例中，我们使用了优化迭代方法。

更新于: 2023年4月3日

246 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告