一维数组 #
数组常被用来当做栈、堆和队列的容器，除此之外，大多是单纯只涉及数组的题目。
特点：
- 支持下标
- 支持切片
- 有固定长度或可变长度
应用场景 #
数组结构很简单，但是出的题涉及的算法类型比较多，比如排序、二分法、双指针、滑动窗口，还会有一些是动态规划。
常用技巧 #
双指针 #
双指针还有快慢指针和左右指针的区别，这里基本都是左右指针，快慢指针一般会应用在循环链表的数据结构里。
var removeDuplicates = function(nums) {
const n = nums.length;
if (n === 0) {
return 0;
}
let fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] !== nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
};
滑动窗口 #
双指针的进阶方案就是滑动窗口，两种方案的思路差不多。
剑指 Offer II 008. 和大于等于 target 的最短子数组
二分查找 #
双指针只能逐个遍历，如果算法本身就需要是排序数组，还可以考虑是否可以用二分查找解决，效率会更高。
如果是求连续子数组的问题，很显然不能进行排序。
前缀和 #
前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。多数时候还需要考虑配合散列表一起，是比较巧妙的解法。
func subarraySum(nums []int, k int) int {
count, pre := 0, 0
m := map[int]int{}
m[0] = 1
for i := 0; i < len(nums); i++ {
pre += nums[i]
if _, ok := m[pre - k]; ok {
count += m[pre - k]
}
m[pre] += 1
}
return count
}
剑指 Offer II 011. 0 和 1 个数相同的子数组
二维数组 #
二维数组的题目偶尔也会有，需要至少掌握基本的数据结构操作和几个例题。
JavaScript #
var arr = new Array(10); //表格有10行
for(var i = 0;i < arr.length; i++){
arr[i] = new Array(10).fill(0); //每行有10列
}
Golang #
package main
import "fmt"
func main() {
// Step 1: 创建数组
values := [][]int{}
// Step 2: 使用 append() 函数向空的二维数组添加两行一维数组
row1 := []int{1, 2, 3}
row2 := []int{4, 5, 6}
values = append(values, row1)
values = append(values, row2)
// Step 3: 显示两行数据
fmt.Println("Row 1")
fmt.Println(values[0])
fmt.Println("Row 2")
fmt.Println(values[1])
// Step 4: 访问第一个元素
fmt.Println("第一个元素为：")
fmt.Println(values[0][0])
}
//Row 1
//[1 2 3]
//Row 2
//[4 5 6]
//第一个元素为：
//1