使用Golang的双指针方法找到给定和的最长子数组

在这篇Golang文章中，我们将使用迭代和优化的迭代方法使用双指针方法来找到给定和的最长子数组。数组是具有相同数据类型的元素集合，这些元素排成连续的内存块，并使用索引或下标访问。

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

在此方法中，我们将定义一个longestSubarray（）函数，使用迭代方法来使用双指针方法找到给定和的最长子数组。

算法

• 第1步 -首先，我们需要导入fmt包。

• 第2步 -启动main（）函数。在main（）函数内部，初始化一个数组并提供整数和值。

• 第3步 —现在，将数组和和传递给它作为参数调用longestSubarray（）函数。

• 第4步 —进一步，使用fmt.Println（）函数打印结果最长的子数组值。

• 第5步 —现在，创建一个longestSubarray（）函数，该函数接受整数数组和和值作为输入。此函数将返回具有给定总和的最长子数组。

• 第6步 —在longestSubarray（）函数中，检查数组的长度。如果它为0，则函数返回nil。

• 第7步 —函数循环遍历带有索引结尾的数组的每个元素以从0开始。在每次迭代中，将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]
}

输出

最长子数组的总和为90是[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("没有找到具有给定总和的子数组")
   } else {
      fmt.Println("具有给定总和的最长子数组：", longestSubarray)
   }
}

输出

具有给定总和的最长子数组：[10 40 20]

结论

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