# 数组和双指针

https://github.com/Twelveeee/AlgorithmCamp2023/tree/main/03_array

# 算法题

# 1. 单调数列

https://leetcode.cn/problems/monotonic-array/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_1/topic_1.go

如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j ， nums[i] <= nums[j] ，那么数组 nums 是单调递增的。如果对于所有 i <= j ， nums[i]> = nums[j] ，那么数组 nums 是单调递减的。
当给定的数组 nums 是单调数组时返回 true ，否则返回 false 。

	func isMonotonic(nums []int) bool {
	return sort.IntsAreSorted(nums) \|\| sort.IsSorted(sort.Reverse(sort.IntSlice(nums)))
	}

	func isMonotonicV2(nums []int) bool {
	flagA, flagB := true, true

	for i := 0; i <= len(nums)-2; i++ {
	if nums[i] < nums[i+1] {
	flagA = false
	}
	if nums[i] > nums[i+1] {
	flagB = false
	}

	if !flagA && !flagB {
	return false
	}
	}

	return flagA \|\| flagB
	}

# 2. 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_1/topic_2.go

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
** 注意：** 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况， nums1 的初始长度为 m + n ，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。 nums2 的长度为 n 。。
解法 1 合并数组后排序
解法 2 双指针 temp 数组
解法 3 逆向双指针存入 nums1 数组

	func merge(nums1 []int, m int, nums2 []int, n int) {
	index1, index2 := m-1, n-1
	tail := m + n - 1
	curr := 0
	for index1 >= 0 && index2 >= 0 && tail > 0 {
	if nums1[index1] > nums2[index2] {
	curr = nums1[index1]
	index1--
	} else {
	curr = nums2[index2]
	index2--
	}

	nums1[tail] = curr
	tail--
	}

	for index1 >= 0 {
	nums1[tail] = nums1[index1]
	tail--
	index1--
	}
	for index2 >= 0 {
	nums1[tail] = nums2[index2]
	tail--
	index2--
	}
	}

# 3. 移除元素

https://leetcode.cn/problems/remove-element/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_2/topic_1.go

给你一个数组 nums 和一个值 val ，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法 1 快慢指针，慢指针为真实值，快指针为遍历值
解法 2 头尾指针，尾指针为被删除的数据

	func removeElement(nums []int, val int) int {
	low, high := 0, len(nums)-1
	for low <= high {
	if nums[low] == val {
	for low <= high && nums[high] == val {
	high--
	}
	if high <= low {
	break
	}
	nums[low], nums[high] = nums[high], nums[low]
	high--
	}
	low++
	}
	return low
	}

# 4. 按奇偶排序数组

https://leetcode.cn/problems/sort-array-by-parity/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_2/topic_2.go

给你一个整数数组 nums ，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
解法 1 新数组
解法 2 头尾指针，尾指针为奇数数据

	func sortArrayByParity(nums []int) []int {
	low, high := 0, len(nums)-1

	for low <= high {
	if nums[low]%2 == 1 {
	nums[low], nums[high] = nums[high], nums[low]
	high--
	} else {
	low++
	}
	}

	return nums
	}

# 5. 轮转数组

https://leetcode.cn/problems/rotate-array/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_2/topic_3.go

给定一个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
解法 1 临时数组
解法 2 双指针交换
解法 3 数组翻转，先整体翻转，

	func rotate(nums []int, k int) {
	len := len(nums)
	newNums := make([]int, len)
	for i, v := range nums {
	newNums[(i+k)%len] = v
	}

	copy(nums, newNums)
	}

# 6. 汇总区间

https://leetcode.cn/problems/summary-ranges/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_2/topic_4.go

给定一个 无重复元素 的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说， nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b" ，如果 a != b
"a" ，如果 a == b

	func summaryRanges(nums []int) []string {
	ans := make([]string, 0, 21)
	start, end := 0, 0

	for i := 0; i < len(nums); i++ {
	end = i
	if i == len(nums)-1 \|\| nums[i]+1 != nums[i+1] {
	if start == end {
	ans = append(ans, strconv.Itoa(nums[start]))
	} else {
	ans = append(ans, strconv.Itoa(nums[start])+"->"+strconv.Itoa(nums[end]))
	}
	start = i + 1
	}
	}

	return ans
	}

# 7. 只出现一次的数字

https://leetcode.cn/problems/single-number/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_3/topic_1.go

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解法 1 排序后找
解法 2 set
解法 3 位运算

	func singleNumber(nums []int) (ans int) {
	for _, v := range nums {
	ans = ans ^ v
	}
	return ans
	}

# 8. 颜色分类

https://leetcode.cn/problems/sort-colors/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/03_array/level_3/topic_2.go

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

	func sortColors(nums []int) {
	low, high := 0, len(nums)-1
	i := 0
	for i <= high {
	if nums[i] == 0 {
	nums[i], nums[low] = nums[low], nums[i]
	low++
	i++
	} else if nums[i] == 2 {
	nums[i], nums[high] = nums[high], nums[i]
	high--
	} else {
	i++
	}
	}

	}

数据结构算法