数组

func twoSum(nums []int, target int) []int {
     数组的长度, 一般底层通过专门的变量来存储长度
     所以其时间复杂度为 O(1)
    lens := len(nums)


    for i:=0; i<lens-1; i++ {


         求另外一个加数
        tmp := target - nums[i]


         从当前元素的后面开始找该加数
         寻找的时间复杂度为 O(n)
         当然这里如果数组特别长，可以
         二分查找等加速，但是这里考察
         的是数组，因此暂时不用考虑
        for j:=i+1; j<lens; j++ {
            if nums[j] == tmp {
                 题目中讲到每种输入只对应一个答案
                 因此只要符合条件，返回即可
                return []int{i, j}
            }
        }
    }


    return nil
}

func threeSum(nums []int) [][]int {
    size := len(nums)


    if size < 3 {
        return nil
    }


    // 预分配一定的空间，保证不频繁开空间导致的额外开销
    res := make([][]int, 0, 5)


    // 排好序，从小到大排序
    sort.Ints(nums)


    // size-2，三数之和, 保证当前元素后面流出2个元素
    for i:=0; i<size-2; i++ {


        // nums[i] > 0: 已经排好序，第一个数都大于0，那么后面加起来肯定大于0，直接跳过
        // i>0 && nums[i]==nums[i-1]: 说明当前这个数已经在上次循环中计算过了
        if nums[i] > 0 || (i>0 && nums[i] == nums[i-1]) {
            continue
        }


        // 另外两个数采用 “两端夹逼法"
        j, k := i+1, size-1


        for j < k {
            // 求和
            sum := nums[i] + nums[j] + nums[k] 
            if sum == 0 {
                // 添加结果
                res = append(res, []int{nums[i], nums[j], nums[k]})


                // 向中间逼近,nums[j-1] == nums[j] 还是要排除重复的，否则
                // 重复计算会导致超时
                j++
                for j<k && nums[j-1] == nums[j] {
                    j++
                }


                // 向中间逼近, nums[k] == nums[k+1] 还是要排除重复的，否则
                // 重复计算会导致超时
                k--
                for j<k && nums[k] == nums[k+1] {
                    k--
                }
            } else if sum > 0 {
                // sum > 0 表示右边的数太大，应当缩小，所以索引 k 向
                // 左边移动，同时移动过程中应当过滤掉已经计算过的数,也就
                // 是 num[k] == num[k-1]
                k--
                for j<k && nums[k] == nums[k+1] {
                    k--
                }
            } else {
                // sum < 0 表示左边的数太小，应当增大，所以索引 j 向
                // 右边移动，同时移动过程中应当过滤掉已经计算过的数,也就
                // 是 num[j] == num[j+1]
                j++
                for j<k && nums[j-1] == nums[j] {
                    j++
                }
            }
        }
    }


    return res
}

func moveZeroes(nums []int)  {
    // 双指针法，slow <= fast
    // fast 指向扫描指针
    slow, fast := 0, 0


    for ; fast<len(nums); i++ {
        // 扫描遇到的元素是否为 0
        if nums[fast] != 0 {
            // 遇到元素不为0，两种情况
            // fast = slow, 表示slow 追得上 fast，原因是当前还没有扫描到 0，此时不用做任何操作，
            //              只需要 slow 跟着fast移动就好
            // fast > slow, 表示由于出现了0导致slow落后fast，而且slow此时指向fast之前为0的位置,
            //              此时需要 slow 处的 0 和 fast 处的非 0 交换
            if fast != slow {
                nums[slow], nums[fast] = nums[fast], nums[slow]
            }


            // 只要出现非0的元素，慢指针 slow 都需要移动
            slow++
        }
    }
}

func climbStairs(n int) int {
    // 1 -> [(1)] -> 1
    // 2 -> [(1, 1), (2)] -> 2
    // 3 -> [(1, 1, 1), (1, 2), (2, 1)] -> climb[1] = climb[2] + climb[1] = 3
    if n <= 2 {
        return n
    }


    // 存储两阶台阶的结果
    arr := []int{1, 2}


    for i:=3; i<=n; i++ {
        steps := arr[1] + arr[0]
        arr[0] = arr[1]
        arr[1] = steps
    }


    return arr[1]
}

func maxArea(height []int) int {
    size := len(height)


    // max 保存最大容量
    // left 容器的做边沿坐标
    // right 容器的右边沿坐标
    max, left, right := 0, 0, size - 1


    // 终止条件，左边沿和有边沿不能重合
    for left < right{
        // 计算容器的宽度 和 长度
        width := right - left
        hight := minInt(height[right], height[left]) 


        // 面积 tmp = 宽度 * 高度
        if tmp := width * hight; tmp > max {
            // 存储最大
            max = tmp
        }


        // 移动边沿低的那一边, 通过两段低的一段
        // 逐渐逼近，最终得到最优的解
        if height[left] > height[right] {
            right--
        } else {
            left++
        }
    }


    return max
}


func minInt(x, y int) int {
    if x < y {
        return x
    }


    return y
}