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

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

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

在这种方法中，我们将定义一个名为longestSubarray()的函数，使用迭代方法来使用双指针方法找到具有给定和的最长子数组。

步骤

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

• 第二步 - 开始main()函数。在main()函数内部，初始化一个数组并提供整数和值。

• 第三步 - 现在，调用longestSubarray()函数并将数组和和一起作为参数传递给它。

• 第四步 - 接下来，使用fmt.Println()函数打印出结果最长子数组的值。

• 第五步 - 现在，创建一个名为longestSubarray()的函数，它接受一个整数数组和一个和值作为输入。这个函数将返回具有给定和的最长子数组。

• 第六步 - 在longestSubarray()函数中，检查数组的长度。如果长度为0，函数返回nil。

• 第七步 - 该函数循环遍历数组的每个元素，索引end从0开始。在每次迭代中，将arr[end]的值添加到currSum中。

• 第八步 - 最后，经过比较后，返回具有给定和的结果最长子数组。

示例

以下是使用迭代方法的双指针方法在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语言程序，并给出了两个示例。在第一个示例中，我们使用了迭代的方法，而在第二个示例中，我们使用了优化迭代的方法。