Golang双指针算法实现

目标:给定目标值,得出(顺序/非顺序)切片两元素和为目标值的两个下标
  • 方案1(嵌套遍历,不保证顺序)
    //         0  1  2  3  4  5  6  7
    s := []int{1, 2, 4, 3, 5, 6, 7, 8}
    t := 15
    var res [][]int
    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s); j++ {
            if s[i]+s[j] == t {
                res = append(res, []int{i, j})
            }
        }
    }
    fmt.Println(res)  // [[1 7] [2 5] [3 6]]
  1. 嵌套循环不解释
  • 方案2(双指针,必须保证升序||降序)
    var res2 [][]int
    t := 10
    s2 := []int{1, 2, 3, 4, 5, 6, 8}
    f, l := 0, len(s2)-1
    for {
        sun := s2[f] + s2[l]
        if sun == t {
            if sun == t {
                if f != l {
                    res2 = append(res2, []int{f, l})
                }
                f++
            }
        }
        if sun < t {
            f++
        }
        if sun > t {
            l--
        }
        if f > l {
            break
        }
    }
    fmt.Println(res2) // [[1 6] [3 5]]
  1. 双指针即:从头部与尾部同时进行,当两个下标的和小于目标值时,头部‘指针’向右移动,当两个下标和大于目标值时,尾部‘指针’向左移动,直到两个'指针'重合循环结束,可以看出,如果是乱序就没什么用处了
  2. 相比于方案1,方案2只需要遍历len(slice)/2次,但是需要顺序保证。
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容