数组与切片

数组是最基本的数据结构，几乎所有的编程语言都内置了它。在 Go 中，数组的使用反而比较少见——我们绝大多数时候用的是切片（slice）。切片在底层是对数组的一层封装，理解它的内存模型和扩容机制，是写出正确、高效 Go 代码的前提。本篇将从数组与切片的区别讲起，深入切片底层结构，然后覆盖双指针、滑动窗口、前缀和、差分数组等经典算法技巧，最后结合 LeetCode 真题演练。这些技巧是面试的高频考点，也是工程中处理批量数据的基础工具。

一、数组 vs 切片：Go 中的区别

很多初学者会把数组和切片混为一谈，但它们在 Go 中是两种截然不同的类型：

特性	数组 `[N]T`	切片 `[]T`
长度	固定，是类型的一部分	可变，运行时可增减
内存	连续，栈上分配（多数情况）	底层数组连续，切片头在栈/堆
传参	值拷贝整个数组	拷贝切片头（指针+len+cap）
比较	可用 `==` 比较内容	不可直接比较（只能与 nil 比）
零值	各元素为零值	nil

数组长度是类型一部分意味着 [3]int 和 [4]int 是完全不同的类型，无法互相赋值。这导致数组在泛型编程中几乎不可用，所以算法题里我们只用切片。

package main

import "fmt"

func main() {
	// 数组：长度固定
	var arr [5]int = [5]int{1, 2, 3, 4, 5}
	fmt.Println("数组:", arr, "长度:", len(arr))

	// 切片：长度可变
	s := []int{1, 2, 3}
	fmt.Println("切片:", s, "长度:", len(s), "容量:", cap(s))

	// 从数组切出切片：共享底层数组
	sub := arr[1:4] // [2 3 4]
	sub[0] = 999
	fmt.Println("修改 sub 后 arr:", arr) // arr[1] 变成 999

	// 数组可以直接用 == 比较
	a := [3]int{1, 2, 3}
	b := [3]int{1, 2, 3}
	fmt.Println("数组相等?", a == b)

	// 切片不能直接 ==，编译会报错
	// var s1, s2 []int = []int{1}, []int{1}
	// fmt.Println(s1 == s2) // 编译错误
}

二、切片底层原理

理解切片的底层结构，是避免一系列「诡异 bug」的关键。

1. SliceHeader：ptr、len、cap

切片在运行时用一个 SliceHeader 结构表示，包含三个字段：

// runtime/slice.go 中的等价结构（简化）
type SliceHeader struct {
	Data uintptr // 指向底层数组的指针
	Len  int     // 当前长度
	Cap  int     // 当前容量
}

Data：指向底层数组起始元素的指针。
Len：切片当前包含的元素个数，len() 返回它。
Cap：底层数组从 Data 开始的可用容量，cap() 返回它。

当我们把切片传给函数时，传递的就是这个 24 字节（64 位机器）的结构体的副本。所以函数内修改 s[i] 会影响外部（共享底层数组），但 append 后若扩容，新切片就指向了新数组。

package main

import "fmt"

func inspectSlice(s []int) {
	fmt.Printf("addr=%p len=%d cap=%d\n", &s[0], len(s), cap(s))
}

func main() {
	s := make([]int, 3, 5)
	for i := range s {
		s[i] = i * 10
	}
	inspectSlice(s) // 打印底层数组首元素地址、长度、容量

	// append 不超过 cap 时，底层数组不变
	s = append(s, 100)
	inspectSlice(s)

	// append 超过 cap 时，会分配新数组
	fmt.Println("扩容前 cap:", cap(s))
	s = append(s, 1, 2, 3)
	fmt.Println("扩容后 cap:", cap(s))
	inspectSlice(s)
}

2. 扩容机制：Go 1.18+ 的新规则

切片 append 超过容量时会触发扩容，新容量的计算规则在 Go 1.18 前后有明显变化：

Go 1.18 之前：当原 cap < 1024 时翻倍，否则按 1.25 倍增长。
Go 1.18 及之后：采用更平滑的策略。原 cap < 256 时翻倍；超过 256 后按公式 newcap = oldcap + (oldcap+3*256)/4 增长，大致是 1.25 倍但更平滑。
最终容量还会根据内存对齐做微调（让元素总大小符合 mallocgc 的尺寸类）。

package main

import "fmt"

func main() {
	s := make([]int, 0)
	prevCap := cap(s)
	for i := 0; i < 2000; i++ {
		s = append(s, i)
		if cap(s) != prevCap {
			fmt.Printf("len=%d cap: %d -> %d\n", len(s), prevCap, cap(s))
			prevCap = cap(s)
		}
	}
}

工程建议：如果预先知道切片最终大小，用 make([]T, 0, n) 一次性分配足够容量，能避免多次扩容和数据拷贝，性能提升往往非常显著。

3. 内存连续性

切片底层数组在内存中是连续的，这带来三个重要特性：

O(1) 随机访问：s[i] 直接用首地址 + i*元素大小计算，无需遍历。
CPU 缓存友好：连续内存能充分利用 CPU 缓存行（cache line，通常 64 字节），遍历速度远快于链表。
不利于中间插入删除：在中间插入或删除元素需要移动后续所有元素，O(n) 复杂度。

package main

import "fmt"

// 在下标 idx 处插入元素，O(n)
func insertAt(s []int, idx, val int) []int {
	if idx < 0 || idx > len(s) {
		return s
	}
	s = append(s, 0)
	// 把 idx 及之后的元素整体后移一位
	copy(s[idx+1:], s[idx:len(s)-1])
	s[idx] = val
	return s
}

// 删除下标 idx 处的元素，O(n)
func removeAt(s []int, idx int) []int {
	if idx < 0 || idx >= len(s) {
		return s
	}
	// 用 idx+1 之后的元素覆盖 idx
	copy(s[idx:], s[idx+1:])
	return s[:len(s)-1]
}

func main() {
	s := []int{1, 2, 3, 5}
	s = insertAt(s, 3, 4)
	fmt.Println("插入后:", s) // [1 2 3 4 5]

	s = removeAt(s, 0)
	fmt.Println("删除后:", s) // [2 3 4 5]
}

三、常见算法

1. 双指针

双指针是数组题最核心的技巧，分为两类：两端向中间和快慢指针。

两端向中间

典型场景：原地反转、有序数组两数之和、容器盛水。

package main

import "fmt"

// 两数之和（有序数组）：返回两个下标
func twoSumSorted(nums []int, target int) []int {
	left, right := 0, len(nums)-1
	for left < right {
		sum := nums[left] + nums[right]
		if sum == target {
			return []int{left, right}
		} else if sum < target {
			left++
		} else {
			right--
		}
	}
	return nil
}

func main() {
	nums := []int{1, 2, 3, 4, 6, 8, 11}
	fmt.Println("两数之和 target=10:", twoSumSorted(nums, 10))
}

快慢指针

典型场景：原地去重、删除指定元素、找中点、检测环。

package main

import "fmt"

// 原地删除有序数组中的重复元素，返回新长度
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	slow := 0
	for fast := 1; fast < len(nums); fast++ {
		if nums[fast] != nums[slow] {
			slow++
			nums[slow] = nums[fast]
		}
	}
	return slow + 1
}

// 原地移除所有值为 val 的元素，返回新长度
func removeElement(nums []int, val int) int {
	slow := 0
	for fast := 0; fast < len(nums); fast++ {
		if nums[fast] != val {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return slow
}

func main() {
	nums := []int{1, 1, 2, 2, 3, 4, 4, 5}
	n := removeDuplicates(nums)
	fmt.Println("去重后:", nums[:n])

	nums2 := []int{3, 2, 2, 3, 4, 5, 3}
	n2 := removeElement(nums2, 3)
	fmt.Println("删除 3 后:", nums2[:n2])
}

2. 滑动窗口

滑动窗口用于解决「连续子数组/子串」类问题，核心是维护一个窗口 [left, right]，根据条件扩张右边界或收缩左边界，把暴力 O(n²) 优化到 O(n)。

package main

import "fmt"

// 长度最小的子数组：和 >= target 的最短连续子数组长度
func minSubArrayLen(target int, nums []int) int {
	n := len(nums)
	left, sum, ans := 0, 0, n+1
	for right := 0; right < n; right++ {
		sum += nums[right]
		for sum >= target {
			if right-left+1 < ans {
				ans = right - left + 1
			}
			sum -= nums[left]
			left++
		}
	}
	if ans == n+1 {
		return 0
	}
	return ans
}

func main() {
	nums := []int{2, 3, 1, 2, 4, 3}
	fmt.Println("最小子数组长 target=7:", minSubArrayLen(7, nums))
}

3. 前缀和

前缀和用于快速求区间和。预处理一个 prefix 数组，prefix[i] 表示前 i 个元素的和，则区间 [l, r] 的和为 prefix[r+1] - prefix[l]。

package main

import "fmt"

type NumArray struct {
	prefix []int
}

func NewNumArray(nums []int) *NumArray {
	prefix := make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		prefix[i+1] = prefix[i] + nums[i]
	}
	return &NumArray{prefix: prefix}
}

func (n *NumArray) SumRange(left, right int) int {
	return n.prefix[right+1] - n.prefix[left]
}

func main() {
	nums := []int{-2, 0, 3, -5, 2, -1}
	obj := NewNumArray(nums)
	fmt.Println("sum[0,2]:", obj.SumRange(0, 2))   // 1
	fmt.Println("sum[2,5]:", obj.SumRange(2, 5))   // -1
	fmt.Println("sum[0,5]:", obj.SumRange(0, 5))   // -3
}

4. 差分数组

差分是前缀和的逆运算，用于区间批量增减场景：对区间 [l, r] 每个元素加 c，只需 diff[l] += c, diff[r+1] -= c，最后做一次前缀和还原。

package main

import "fmt"

type Difference struct {
	diff []int
}

func NewDifference(nums []int) *Difference {
	diff := make([]int, len(nums))
	diff[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		diff[i] = nums[i] - nums[i-1]
	}
	return &Difference{diff: diff}
}

// 对区间 [l, r] 每个元素加 val
func (d *Difference) Increment(l, r, val int) {
	d.diff[l] += val
	if r+1 < len(d.diff) {
		d.diff[r+1] -= val
	}
}

func (d *Difference) Result() []int {
	res := make([]int, len(d.diff))
	res[0] = d.diff[0]
	for i := 1; i < len(d.diff); i++ {
		res[i] = res[i-1] + d.diff[i]
	}
	return res
}

func main() {
	nums := []int{1, 2, 3, 4, 5}
	d := NewDifference(nums)
	d.Increment(1, 3, 10) // 下标 1~3 加 10
	d.Increment(2, 4, -5) // 下标 2~4 减 5
	fmt.Println("最终结果:", d.Result())
}

5. 旋转数组

把数组整体向右旋转 k 步。三种解法：暴力 O(nk)、辅助数组 O(n) 空间、三次反转 O(1) 空间。

package main

import "fmt"

// 三次反转法：O(1) 空间
// 1. 反转整个数组
// 2. 反转前 k 个
// 3. 反转后 n-k 个
func rotate(nums []int, k int) {
	n := len(nums)
	k %= n
	if k == 0 {
		return
	}
	reverse(nums, 0, n-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, n-1)
}

func reverse(nums []int, l, r int) {
	for l < r {
		nums[l], nums[r] = nums[r], nums[l]
		l++
		r--
	}
}

func main() {
	nums := []int{1, 2, 3, 4, 5, 6, 7}
	rotate(nums, 3)
	fmt.Println("旋转 3 步:", nums) // [5 6 7 1 2 3 4]
}

6. 原地去重

有序数组去重前面已展示。这里补充一个更通用的「每个元素最多保留两次」的写法：

package main

import "fmt"

// 有序数组，每个元素最多保留两次，返回新长度
func removeDuplicatesII(nums []int) int {
	if len(nums) <= 2 {
		return len(nums)
	}
	slow := 2
	for fast := 2; fast < len(nums); fast++ {
		// nums[fast] 与 nums[slow-2] 不同，说明可以保留
		if nums[fast] != nums[slow-2] {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return slow
}

func main() {
	nums := []int{1, 1, 1, 2, 2, 3}
	n := removeDuplicatesII(nums)
	fmt.Println("最多保留两次:", nums[:n]) // [1 1 2 2 3]
}

四、LeetCode 经典题解析

1. 两数之和（LC 1）

题目：给定一个整数数组 nums 和目标值 target，返回和为 target 的两个元素的下标。假设恰好有一个解。

思路：用哈希表记录已遍历的元素及其下标，对每个 nums[i]，查找 target - nums[i] 是否在表中。O(n) 时间，O(n) 空间。

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	// map: 值 -> 下标
	m := make(map[int]int)
	for i, v := range nums {
		if j, ok := m[target-v]; ok {
			return []int{j, i}
		}
		m[v] = i
	}
	return nil
}

func main() {
	nums := []int{2, 7, 11, 15}
	fmt.Println("两数之和 target=9:", twoSum(nums, 9)) // [0 1]
}

2. 三数之和（LC 15）

题目：找出数组中所有和为 0 的不重复三元组。

思路：排序后固定一个数 nums[i]，再用双指针在剩余部分找两数之和为 -nums[i]。难点在去重：固定数和左右指针都要跳过重复值。O(n²) 时间。

package main

import (
	"fmt"
	"sort"
)

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var result [][]int
	n := len(nums)

	for i := 0; i < n-2; i++ {
		// 剪枝：最小的数已大于 0，不可能凑出 0
		if nums[i] > 0 {
			break
		}
		// 固定数去重
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i+1, n-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				// 左右指针去重
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if sum < 0 {
				left++
			} else {
				right--
			}
		}
	}
	return result
}

func main() {
	nums := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println("三数之和:", threeSum(nums)) // [[-1 -1 2] [-1 0 1]]
}

3. 盛最多水的容器（LC 11）

题目：数组中每个元素表示竖线高度，两根竖线与 x 轴围成的容器能盛多少水，求最大值。

思路：双指针从两端向中间收缩，每次移动较矮的那根（因为移动高的不可能让面积变大）。O(n) 时间。

package main

import "fmt"

func maxArea(height []int) int {
	left, right := 0, len(height)-1
	ans := 0
	for left < right {
		h := height[left]
		if height[right] < h {
			h = height[right]
		}
		area := h * (right - left)
		if area > ans {
			ans = area
		}
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return ans
}

func main() {
	height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
	fmt.Println("最大盛水:", maxArea(height)) // 49
}

4. 最长无重复子串（LC 3）

题目：找出字符串中不含重复字符的最长子串长度。

思路：滑动窗口 + 哈希表。维护窗口 [left, right]，用 map 记录字符最近出现位置，遇到重复就把 left 跳到重复字符下一位。

package main

import "fmt"

func lengthOfLongestSubstring(s string) int {
	last := make(map[byte]int)
	left, ans := 0, 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		if idx, ok := last[c]; ok && idx >= left {
			left = idx + 1
		}
		last[c] = right
		if right-left+1 > ans {
			ans = right - left + 1
		}
	}
	return ans
}

func main() {
	fmt.Println("abcabcbb:", lengthOfLongestSubstring("abcabcbb")) // 3
	fmt.Println("bbbbb:", lengthOfLongestSubstring("bbbbb"))       // 1
	fmt.Println("pwwkew:", lengthOfLongestSubstring("pwwkew"))     // 3
}

五、复杂度分析汇总

算法	时间复杂度	空间复杂度	备注
随机访问 `s[i]`	O(1)	O(1)	连续内存优势
头部插入/删除	O(n)	O(1)	需移动元素
尾部插入（不扩容）	O(1)	O(1)	均摊
双指针查找	O(n)	O(1)	两端或快慢
滑动窗口	O(n)	O(1) 或 O(字符集)	每个元素进出窗口一次
前缀和	预处理 O(n)，查询 O(1)	O(n)	区间和利器
差分数组	修改 O(1)，还原 O(n)	O(n)	区间批量修改
旋转数组（三反转）	O(n)	O(1)	推荐

六、小结

数组与切片是 Go 中最常用的数据结构，本篇要点回顾：

数组 vs 切片：数组长度是类型一部分、值传递；切片是数组的应用层封装，传参只拷贝 24 字节切片头。算法题里几乎只用切片。
切片底层：SliceHeader 包含 Data、Len、Cap 三个字段。Go 1.18+ 扩容规则为：cap < 256 翻倍，之后约 1.25 倍平滑增长。预先知道大小时用 make([]T, 0, n) 避免多次扩容。
内存连续性带来 O(1) 随机访问和缓存友好，但中间插入删除是 O(n)。
双指针是数组题的灵魂：两端向中间适合有序数组、容器类；快慢指针适合原地修改、去重、找中点。
滑动窗口把连续子数组问题从 O(n²) 优化到 O(n)，关键是「扩张右边界、收缩左边界」的单调性。
前缀和用于区间和查询，差分数组用于区间批量修改，二者互为逆运算。
三次反转实现 O(1) 空间旋转数组，是经典的「巧用反转」思路。

下一篇我们将离开连续内存，进入指针串接的链表世界。链表与数组在很多场景下是互补的：插入删除频繁选链表，随机访问频繁选数组。理解它们的取舍，是数据结构选型的基本功。

入门篇

进阶篇

资深篇

数组与切片

一、数组 vs 切片：Go 中的区别

二、切片底层原理

1. SliceHeader：ptr、len、cap

2. 扩容机制：Go 1.18+ 的新规则

3. 内存连续性

三、常见算法

1. 双指针

两端向中间

快慢指针

2. 滑动窗口

3. 前缀和

4. 差分数组

5. 旋转数组

6. 原地去重

四、LeetCode 经典题解析

1. 两数之和（LC 1）

2. 三数之和（LC 15）

3. 盛最多水的容器（LC 11）

4. 最长无重复子串（LC 3）

五、复杂度分析汇总

六、小结

数组与切片 ​

一、数组 vs 切片：Go 中的区别 ​

二、切片底层原理 ​

1. SliceHeader：ptr、len、cap ​

2. 扩容机制：Go 1.18+ 的新规则 ​

3. 内存连续性 ​

三、常见算法 ​

1. 双指针 ​

两端向中间 ​

快慢指针 ​

2. 滑动窗口 ​

3. 前缀和 ​

4. 差分数组 ​

5. 旋转数组 ​

6. 原地去重 ​

四、LeetCode 经典题解析 ​

1. 两数之和（LC 1） ​

2. 三数之和（LC 15） ​

3. 盛最多水的容器（LC 11） ​

4. 最长无重复子串（LC 3） ​

五、复杂度分析汇总 ​

六、小结 ​

数组与切片

一、数组 vs 切片：Go 中的区别

二、切片底层原理

1. SliceHeader：ptr、len、cap

2. 扩容机制：Go 1.18+ 的新规则

3. 内存连续性

三、常见算法

1. 双指针

两端向中间

快慢指针

2. 滑动窗口

3. 前缀和

4. 差分数组

5. 旋转数组

6. 原地去重

四、LeetCode 经典题解析

1. 两数之和（LC 1）

2. 三数之和（LC 15）

3. 盛最多水的容器（LC 11）

4. 最长无重复子串（LC 3）

五、复杂度分析汇总

六、小结