数组

Last renew: June 3, 2022 pm

数组题型刷题总结

注：本文仅为个人学习笔记，无任何版权。

数组：存放在连续空间的相同类型元素的集合，一般不进行删除操作。

两点注意；

  1. 数组下标都是从0开始
  2. 数组内存空间地址连续（增添删除都很麻烦）

二维数组在系统中的存储方式

m*n的二维数组来说，一般由一个头节点指向一个长为n的一维列数组，每个列数组又作为另一个长为m的一维行数组的头节点。

并不是连续地址空间

一般看到链表/子串/数组之类的题，直接上双指针就行

常用方法：

  1. 二分法
  2. 双指针
  3. 滑动窗口
  4. 模拟行为

1. 二分法

704, 35, 34, 69, 367

限制条件：有序数组 且 无重复元素

Key：边界条件的设定。在二分查找过程中，每次区间变化都遵守边界条件不变。

常用区间：[lo, hi], [lo, hi)

注：乘法溢出时用除法处理即可。

暴力解法一般时间复杂度为O(N)

二分法一般时间复杂度为O(logN)

2. 双指针

27, 26, 283, 844, 977

双指针技巧可以分为两类：【快慢指针】和【左右指针】。前者解决链表中的问题，比如判断链表是否包含环；后者主要解决数组（字符串）中的问题，二分查找也是左右指针的一种特殊情况。

常见的双指针问题还有移除元素/移除字符串等。

快慢指针常见问题：链表操作/找中点/归并排序/链表环

左右指针常见问题：反转数组/二分搜索

暴力解法时间复杂度一般为O(N^2)

双指针法时间复杂度一般为O(N)

3. 滑动窗口

209, 904, 76

实际上滑动窗口也是一种特殊的双指针。不过因为其在子串问题中的优异表现，我将其单独作为一个部分来讲。

滑动窗口算法的大致逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = 0;

while (right < s.size()) {
  //增大窗口
  window.add(s[right]);
  right++;
  
  while (window needs shrink) {
    //缩小窗口
    window.remove(s[left]);
    left++;
  }
}

时间复杂度O(N)， 比一般的字符串暴力算法高效的多。

滑动窗口的关键在于各种细节问题。比如如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。即使你明白了这些细节，也容易报错。

使用一套来自labuladong 的滑动窗口代码框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> need = new HashMap<>();
//需要的字符传入need
for (char c : t.toCharArray()) {
  need. put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
while (right < s.length()) {
  //c是移入窗口的字符
  char c = s.charAt(right);
  //右边界右移
  right++;
  
  //进入窗口的一系列操作.....
  
  //当满足时，进行窗口缩减
  while (window needs shrink) {
    char d = s.charAt(left);
    //左边界右移
    left++;
    
    //出窗口
  }
}

4. 模拟行为

48， 54， 59

不涉及太多算法，单纯模拟，考验对代码的掌控能力。

循环不变量原则十分重要。

真正解决题目的代码都是简洁的，有原则性的。

刷题记录+题解

LC3