数组是存放在连续内存空间上的相同类型数据的集合。

需要两点注意的是

  • 数组下标都是从0开始的。

  • 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

数组的元素是不能删的，只能覆盖。

二分查找

只要看到给出的数组是有序数组，都可以想一想是否可以使用二分法

  • 暴力解法时间复杂度：O(n)
  • 二分法时间复杂度：O(logn)

搜索插入的位置

Leetcode：35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {	// 区间是左闭右闭
        mid := left + ((right - left)/2)
        if nums[mid] < target{
            left = mid + 1
        } else if nums[mid] > target{
            right = mid - 1
        } else {
            return mid
        }
    }
    // 分别处理如下四种情况
    // 目标值在数组所有元素之前  [0, -1]
    // 目标值等于数组中某一个元素  return middle;
    // 目标值插入数组中的位置 [left, right]，return  right + 1
    // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
    return right + 1
}
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

在排序数组中查找元素的第一个和最后一个位置

X的平方根

Leetcode：69.x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

思路：二分法，由于平方根一定小于它的一半，所以右边界可以减半；其次，由于与插入元素是插入边界右边，所以需要return right + 1，而平方根要求保留整数部分 ，小数部分将被舍去，所以是return right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left := 0
    right := x >> 1 // 平方根一定小于它的一半

    for left <= right {
        mid := left + (right - left) >> 1
        if mid*mid > x {
            right = mid - 1
        } else if mid*mid < x {
            left = mid + 1
        } else {
            return mid
        }
    }
    return right
}

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置

复杂度

  • 暴力解法时间复杂度：O(n^2)
  • 双指针时间复杂度：O(n)

移除元素

Leetcode：27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路：

  1. 暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。但是这样的时间复杂度：O(n^2)。

  2. 双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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++	// 注意此处的slow++是放在上面移动元素之后的，因为是要删除元素，所以先移动元素，再slow++
            }
        }
        return slow
    }
    • 时间复杂度：O(n)
    • 空间复杂度：O(1)

删除有序数组中的重复项

Leetcode：26.删除有序数组中的重复项

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 *只出现一次* ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地*修改输入数组* 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]

输出：2, nums = [1,2]

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路：双指针法，与移除元素题目不同，此处的slow++需要在移动元素代码（nums[slow] = nums[fast]）之前执行，因为是删除重复项，所以slow++后相同元素就保留下来一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    slow := 0

    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++	// 先slow++，保留下重复项中的一个元素
            nums[slow] = nums[fast]
        }
    }

    return slow + 1
}

移动零

Leetcode：283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

思路：快指针找到不为0的值，然后与指向0值的慢指针交换，让0后移，再移动慢指针。

1
2
3
4
5
6
7
8
9
10
func moveZeroes(nums []int)  {
    slow := 0

    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != 0 { // 快指针不为0时，就与慢指针进行交换元素
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

有序数组的平方

Leetcode：977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

1
2
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]

思路：

  1. 每个数平方之后，排个序，这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度

  2. 双指针法：数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

    i指向起始位置，j指向终止位置。

    定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

    如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

    如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func sortedSquares(nums []int) []int {
    size := len(nums)
    i, j, k := 0, size - 1, size - 1

    res := make([]int, size)

    for i <= j {
        if nums[i]*nums[i] < nums[j]*nums[j] {
            res[k] = nums[j]*nums[j]
            k--
            j--
        } else {
            res[k] = nums[i]*nums[i]
            k--
            i++
        }
    }

    return res
}

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。

模拟栈

匹配问题都是模拟栈的强项

比较含退格的字符串

Leetcode：844.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

1
2
3
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

思路：模拟栈方法，如果字符不为#，就把字符添加到栈里，如果字符为#，并且栈不为空，则弹出栈中的字符（相当于消除字符），最后对比两个栈是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func backspaceCompare(s string, t string) bool {
    return process(s) == process(t)
}

func process(str string) string{
    stk := []byte{} // 模拟栈

    for fast := 0; fast < len(str); fast++ {
        if str[fast] != '#' {
            stk = append(stk, str[fast])
        } else if len(stk) > 0 { // 等于'#'，就从栈中弹出一个字符
            stk = stk[:len(stk) - 1]
        }
    }

    return string(stk)
}

时间复杂度为O(n)

空间复杂度：由于使用了额外的空间模拟栈，所以为O(n)

滑动窗口

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。

  • 暴力解法时间复杂度：O(n^2)
  • 滑动窗口时间复杂度：O(n)

模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 首先明确一点(left, right]为所求区间
func module(nums []int) {
	n := len(nums)
	// 左指针
  left := -1
	
  // 记录最短区间长度
	res := n + 1
	
	for right := 0; right < n; right++ {
		// 加入nums[i]之前，(left, right - 1]可能不满足条件
		// 1. 直接将A[i]加到区间，形成(left, right]
		// 2. 更新区间状态
		for 区间超出/满足条件 {
			res = min(res, right - left)
			// 3. 移除nums[++left]
			// 4. 更新区间的状态
		}
		// assert 区间(left, right]到这里肯定不满足条件
	}
	return	res
}

长度最小的子数组

Leetcode：209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]

  • 输出：2

  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

  • 输入：target = 4, nums = [1,4,4]

  • 输出：1

思路：在本题中实现滑动窗口，主要确定如下三点：

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

定义两个指针，一个快指针代表着滑动窗口的右边界，慢指针代表着左边界，先增大右边界，然后再缩小左边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func minSubArrayLen(target int, nums []int) int {
    resLen, subLen, sum, slow := math.MaxInt32, 0, 0, 0

    // 这个for循环移动的是窗口右边界
    for fast := 0; fast < len(nums); fast++ {
        sum += nums[fast]

        // 当累加的值>=目标值，就移动左边界，并减少累加的值
        for sum >= target {
            subLen = fast - slow + 1
            if subLen < resLen {
                resLen = subLen
            }
            sum -= nums[slow]
            slow++
        }
    }

    if resLen == math.MaxInt32{
        return 0
    }

    return resLen
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

不要以为for里放一个while就以为是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

最小覆盖子串

Leetcode：76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

思路：左右窗口都是从0开始，先移动右窗口，待窗口包含整个字符串t后，再移动左窗口，逐个缩小范围，获取最小子串结果；过程中需要用到两个map遍历，分别保存字符t和保存窗口中字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func minWindow(s string, t string) string {
    // win保存滑动窗口字符集，key是字符，value是字符的个数
    // need保存需要的字符集(t)，值不需要变
    win, need := map[byte]int{}, map[byte]int{}
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    left, right := 0, 0
    match := 0  // match匹配次数

    start, end := 0, 0
    length := math.MaxInt64

    for right < len(s) {
        c := s[right]
        right++ // 右移右窗口

        if _, ok := need[c]; ok {   // 该字符是需要的字符
            win[c]++    // 先保存在窗口字符集里，再做以下判断
            // 因为有些字符可能有多个，所以如果当前字符的数量等于需要的字符的数量，则match值+1
            if win[c] == need[c] {
                match++
            }
        }

        // t中的所有字符都包含进窗口（win）里后，开始缩紧窗口,开始移动左窗口
        for match == len(need) {
            // 获取结果
            if right - left < length {
                length = right - left
                start = left
				end = right
            }
            d := s[left]
            left++

            // 该字符不是需要的字符，就继续缩减左窗口，
            // 如果是需要的字符，就跳出循环，增大右窗口
            if _, ok := need[d]; ok {
                if win[c] == need[d] {
                    match--
                }
                win[d]--    // 必须先做以上if判断，才能缩减窗口
            }
        }
    }

    if length == math.MaxInt64 {
        return ""
    }

    return s[start:end]
}

字符串的排列

Leetcode：567.字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

1
2
3
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

思路：由于只需要判断s2中是否包含s1的排列，所以窗口中的个数不能大于s1的个数，用right - left >= len(s1)作为移动左指针的条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func checkInclusion(s1 string, s2 string) bool {
    // win保存滑动窗口字符集，key是字符，value是字符的个数
    // need保存需要的字符集(s1)，值不需要变
    win, need := map[byte]int{}, map[byte]int{}
    for i := 0; i < len(s1); i++ {
        need[s1[i]]++
    }

    left, right := 0, 0
    match := 0  // match匹配次数

    for right < len(s2) {
        c := s2[right]
        right++ // 右移右窗口

        if _, ok := need[c]; ok {   // 该字符是需要的字符
            win[c]++    // 先保存在窗口字符集里，再做以下判断
            // 因为有些字符可能有多个，所以如果当前字符的数量等于需要的字符的数量，则match值+1
            if win[c] == need[c] {
                match++
            }
        }

        // 当窗口长度大于字符串长度，缩紧窗口
        for right - left >= len(s1) {
            // 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件
            if match == len(need) {
                return true
            }
            d := s2[left]
            left++

            // 该字符不是需要的字符，就继续缩减左窗口，
            // 如果是需要的字符，就跳出循环，增大右窗口
            if _, ok := need[d]; ok {
                if win[c] == need[d] {
                    match--
                }
                win[d]--    // 必须先做以上if判断，才能缩减窗口
            }
        }
    }

    return false
}

无重复字符的最长子串

Leetcode：3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：1、右指针右移；2、根据题意收缩窗口；3、左指针右移更新窗口；4、缩完左窗口后根据题意计算结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func lengthOfLongestSubstring(s string) int {
    if len(s)==0{
        return 0
    }

    res := 1
    win := make(map[byte]int)
    left, right := 0, 0

    for right < len(s) {
        c := s[right]
        right++
        win[c]++
        // 缩小左窗口
        for win[c] > 1 {	// 字符只能出现一个，大于1说明该字符重复了，用大于1作为缩小左窗口条件
            d := s[left]
            left++
            win[d]--
        }
        // 缩完左窗口后才没有重复的子串，这时再计算接口
        tmp := right - left
        if tmp > res {
            res = tmp
        }
    }

    return res
}