1 两数和

在数组中找到 2 个数之和等于给定值的数字，结果返回 2 个数字在数组中的下标。

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

思路：
哈希，遍历 O(n)

4 中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

思路：
有序 -> 二分
转化为寻找第K个数
分别对num1和num2进行二分，
A[k/2] 和B[k/2]比较，较小的可以直接排除。
截断条件思考：

k/2超出了数组范围，在另外一个数组选取就好
当两个指针的和满足k时，截断。

明确k的含义：第k个数

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    if (m+n) % 2 == 1{
        return float64(getKthElement(nums1, nums2, (m+n+1)/2))
    } else {
        return float64(getKthElement(nums1, nums2, (m+n)/2) + getKthElement(nums1, nums2, (m+n)/2+1))/2
    }
}

func getKthElement(nums1, nums2 []int, k int) int {
    index1, index2 := 0, 0
    for {
        if index1 == len(nums1) {
            return nums2[index2 + k - 1]
        }
        if index2 == len(nums2) {
            return nums1[index1 + k - 1]
        }
        if k == 1 {
            return min(nums1[index1], nums2[index2])
        }
        half := k/2
        newIndex1 := min(index1 + half, len(nums1)) - 1
        newIndex2 := min(index2 + half, len(nums2)) - 1
        pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
        if pivot1 <= pivot2 {
            k -= (newIndex1 - index1 + 1)
            index1 = newIndex1 + 1
        } else {
            k -= (newIndex2 - index2 + 1)
            index2 = newIndex2 + 1
        }
    }
    return 0
}

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

作者：qian-long-wu-yong-11
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/by-qian-long-wu-yong-11-0ild/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

11 最多雨水

给出一个非负整数数组 a1，a2，a3，…… an，每个整数标识一个竖立在坐标轴 x 位置的一堵高度为 ai 的墙，选择两堵墙，和 x 轴构成的容器可以容纳最多的水。

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

思路：
双指针，从每次移动高度小的值。并维持一个最多雨水的ans

三数之和

给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：O（n2），先排序，因为不允许重复多次。遍历first，使得second + third = - first。second和third使用双指针，复杂度为O(n)

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

思路：
双指针，慢指针指向待更新的数组下标位置，快指针指向新数组的元素位置。