最近在LeetCode刷到一类数组问题，在这里总结一下，数组问题无非是排序，合并，移位之类的，大致思路是通过指针遍历或双指针从数组两头遍历，还有就是交换思想，这个用的好可以减少空间复杂度。下面是几道算法题的Go语言实现
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例：
- 输入: [0,1,0,3,12]
- 输出: [1,3,12,0,0]
说明：必须在原数组上操作，不能拷贝额外的数组。
冒泡思路： 这道题的思路很简单，如果对冒泡排序思想很熟的话，几分钟就可用写出来，从左到右遍历数组，遇到0就往右冒泡。
代码实现：
func moveZero(array []int) {
for i:=0;i<len(array);i++{
for j:=0;j<len(array)-(i+1);j++{
if array[j]==0 {
// 和前一个元素0交换
temp := array[j]
array[j] = array[j+1]
array[j+1] = temp
}
}
}
}冒泡排序的时间复杂度比较高，对于这道题有更简单的做法，只需要一次遍历，通过快速排序的思想来做
快排思路：快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。这里我们可以用0当做这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]，对照动态图来理解
这个解法是力扣上很漂亮的解法，核心思路的交换。我第一次想到是冒泡的思路，不过快排的思路更加巧妙高效
代码实现：
func moveZeroes1(array []int) {
if array==nil {
return
}
//两个指针i和j
j := 0
for i:=0;i<len(array);i++ {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if array[i]!=0 {
tmp := array[i]
array[i] = array[j]
array[j] = tmp
j = j+1
}
}
}颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
- 输入：nums = [2,0,2,1,1,0]
- 输出：[0,0,1,1,2,2]
示例 2：
- 输入：nums = [2,0,1]
- 输出：[0,1,2]
冒泡思路：在这个题中，红白蓝三个球中，红色的始终会在数组最左边，蓝色的球始终会在数组最右边。那我的想法是遍历数组中的元素，碰到红球就向数组的左边冒泡，碰到蓝球就向数组的右边冒泡，碰到白球就不动。这样由于红球向左移，蓝球向右移，剩下的白球肯定会在中间。问题得以解决
快排思想：快排思想可以很多问题，而且时间复杂度也低，是优化解决数组问题很重要的思想。刚刚用冒泡思路很清晰的解决了问题，但时间复杂度很高，可以用快排思想优化一下，思路也很简单。遍历数组，碰到蓝球就和数组左边的元素交换位置，碰到红球就和数组右边的元素交换位置，碰到白球不动。问题得以解决
代码实现：
func color(array *[]int) {
var left = 0
var right = len(*array)-1
for i:=0;i<=right;{
if (*array)[i]==0 {
temp := (*array)[i]
(*array)[i] = (*array)[left]
(*array)[left] = temp
left++
i++
} else if (*array)[i]==1 {
i++
} else if (*array)[i]==2 {
temp := (*array)[i]
(*array)[i] = (*array)[right]
(*array)[right] = temp
right--
}
}
}合并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
- 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
- 输出：[1,2,2,3,5,6]
示例 2：
- 输入：nums1 = [1], m = 1, nums2 = [], n = 0
- 输出：[1]
解题思路：刚看到这个题目时，我的第一想法的插入，因为给出的两个数组已经是有序的了，所以只需要遍历第一个数组，逐个插入第二个数组中的元素即可，参考插入排序的思路即可解题
代码实现：
func mergeNums(nums1 []int,nums2 []int,m int,n int){
for i:=0;i<n;i++{
e := nums2[i]
var index = 0
for j := m-1+i;j>0 && nums1[j]>e;j--{
nums1[j+1] = nums1[j]
index = j
}
nums1[index] = e
}
}数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
- 输入: [3,2,1,5,6,4] 和 k = 2
- 输出: 5
示例 2:
- 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
- 输出: 4
解题思路： 用冒泡排序的思想，把大的元素向右冒泡，当冒泡到第k个元素时跳出循环，并返回这个元素
代码实现：
// 第k大元素
func numsK(array []int, k int) {
for i:=0;i<len(array);i++{
for j:=0;j<len(array)-i-1;j++{
if array[j] > array[j+1] {
temp := array[j]
array[j] = array[j+1]
array[j+1] = temp
}
}
if k==i+1{
println(array[len(array)-k])
break
}
}
}两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
- 输入：numbers = [2,3,4], target = 6
- 输出：[1,3]
示例 3：
- 输入：numbers = [-1,0], target = -1
- 输出：[1,2]
解题思路： 我第一个想法是两层循环遍历数组，暴力枚举，直到找到满足条件的两个数
代码实现：
func numsPlus(array []int,target int) []int {
for i:=0;i<len(array);i++{
for j:=i+1;j<len(array);j++{
if array[i]+array[j]==target{
return []int{i+1,j+1}
}
}
}
return []int{}
}盛最多水的容器
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
解题思路： 我最先想到是暴力解法，穷举所有的能盛水的方案，然后找出最大的，但是在提交到力扣上时，暴力解法执行超时，所以不是最好的解法。在力扣上有一种O(n)的解法，解题思路如下，使用两个指针，一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。
代码实现：
func water(array []int) int {
i,j :=0,len(array)-1
w,h := 0,0
var max = 0
for ;i<j; {
w = j-i
temp1 := array[i]
temp2 := array[j]
if temp1>temp2{
h = temp2
} else {
h = temp1
}
area := w*h
if area>max {
max = area
}
if temp1>temp2{
j--
}else {
i++
}
}
return max
}下面也贴一下我的暴力解法，时间复杂度是O(n^2)，虽然超时但是思路简单直接
func water(array []int) int {
var max = 0
for i:=0;i<len(array);i++{
for j:=i+1;j<len(array);j++{
temp1 := array[i]
temp2 := array[j]
var temp = 0
if temp1>temp2{
temp=temp2
}else {
temp=temp1
}
area := (j-i)*temp
if area>max {
max = area
}
}
}
return max
}
