数组
- 双指针技巧
- 数组删除、去重
图片来源于网络
1. 双指针技巧
1.1 快慢指针
快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。
1.1.1 判定链表中是否含有环
用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
/**
* 判定链表中是否含有环
*/
private boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) return true;
}
return false;
}
1.1.2 已知链表中含有环，返回这个环的起始位置
当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
/**
* 已知链表中含有环，返回这个环的起始位置
* <p>
* 第一次相遇时，假设慢指针slow走了k步，那么快指针fast一定走了2k步
* fast一定比slow多走了k步，这多走的k步其实就是fast指针在环里转圈圈，所以k的值就是环长度的「整数倍」。
*/
private ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head;
while (slow != fast) {
slow = fast.next;
fast = fast.next;
}
return slow;
}
1.1.3 寻找链表的中点
让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
/**
* 寻找链表的中点
* 当链表的长度是奇数时，slow恰巧停在中点位置；如果长度是偶数，slow最终的位置是中间偏右
*/
private ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
1.1.4 寻找链表的倒数第n个元素
使用快慢指针，让快指针先走n步，然后快慢指针开始同速前进。这样当快指针走到链表末尾null时，慢指针所在的位置就是倒数第n个链表节点（n不会超过链表长度）。
/**
* 寻找链表的倒数第n个元素
* <p>
* 如：给定一个链表删除链表的倒数第n个节点： 1 -> 2 -> 3 -> 4 -> 5 和 n=2，则返回 1 -> 2 -> 3 -> 5
*/
private ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode slow, fast;
slow = fast = head;
// 快指针先前进 n 步
/*for (int i = 0; i < n; i++) {
fast = fast.next;
}*/
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) {
// 如果此时快指针走到头了，
// 说明倒数第 n 个节点就是第一个节点
return head.next;
}
// 让慢指针和快指针同步向前
while (fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// slow.next 就是倒数第 n 个节点，删除它
slow.next = slow.next.next;
return head;
}
1.2 左右指针
左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1。
1.2.1 二分查找
/**
* 二分查找
*/
private int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// [left, right]
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
1.2.2 两数之和
- 给的数组有序
/**
* 两数之和
* <p>
* 给定升序排列，找两个数使其相加之和等于 target，返回这两个数的下标（下标值不是从0开始）
* 如：nums = [2, 7, 10, 12] 和 target = 9
* 输出：[1, 2]
*/
private int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else if (sum > target) {
right--;
}
}
return new int[]{-1, -1};
}
只要数组有序，就可以考虑用双指针技巧。上面题有点类似二分查找，通过调节left和right可以调整sum的大小。
- 给的数组无序
若给的数组无序，使用穷举法如下：
/**
* 给你一个数组和一个整数target，可以保证数组中存在两个数的和为target，请你返回这两个数的索引
* <p>
* 如：输入nums = [3,1,3,6],target = 6，算法应该返回数组[0,2]，因为 3 + 3 = 6
* <p>
* 穷举法：时间复杂度 O(N^2)，空间复杂度 O(1)
*/
private int[] twoSum01(int[] nums, int target) {
// 穷举法
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] + nums[i] == target) {
return new int[]{i, j};
}
}
}
// 不存在
return new int[]{-1, 1};
}
通过一个哈希表减少时间复杂度，优化如下：
/**
* 通过一个哈希表减少时间复杂度
* <p>
* 哈希表的查询时间为 O(1)，算法的时间复杂度降低到 O(N)，但需要 O(N) 的空间复杂度来存储哈希表
*/
private int[] twoSum(int[] nums, int target) {
int n = nums.length;
HashMap<Integer, Integer> index = new HashMap<>();
// 构造一个哈希表：元素映射到相应的索引
for (int i = 0; i < n; i++) {
index.put(nums[i], i);
}
for (int i = 0; i < n; i++) {
int other = target - nums[i];
// 若 other 存在且不是 nums[i] 本身
if (index.containsKey(other) && index.get(other) != i) {
return new int[]{i, index.get(other)};
}
}
return new int[]{-1, 1};
}
此类问题还可以衍生要求设计一个类，拥有两个 API：
class TwoSum {
// 向数据结构中添加一个数 number
public void add(int number);
// 寻找当前数据结构中是否存在两个数的和为 value
public boolean find(int value);
}
使用哈希表辅助 find 方法如下：
Map<Integer, Integer> freq = new HashMap<>();
/**
* 向数据结构添加一个数 number
* <p>
* 时间复杂度，add方法是 O(1)，find方法是 O(N)，空间复杂度为 O(N)
*/
public void add(int number) {
// 记录 number 出现的次数
freq.put(number, freq.getOrDefault(number, 0) + 1);
}
/**
* 寻找当前数据结构中是否存在两个数之和为value
* <p>
* 缺点：若使用find方法非常频繁，那么每次都要 O(N) 的时间，会很浪费费时间
*/
public boolean find(int value) {
for (Integer key : freq.keySet()) {
int other = value - key;
// 情况一：如果连续 add 了 [3,2,3,5]，那么freq是{3:2,2:1,5:1}，执行find(6)，
// 由于 3 出现了两次，3 + 3 = 6，所以返回 true
if (other == key && freq.get(key) > 1) {
return true;
}
// 情况二：freq是{3:2,2:1,5:1}，执行find(7)，那么key为 2，other为 5 时算法可以返回 true
if (other != key && freq.containsKey(other)) {
return true;
}
}
return false;
}
上述针对频繁使用 find 方法的场景还可以优化：
Set<Integer> sum = new HashSet<>();
List<Integer> nums = new ArrayList<>();
public void add(int number) {
// 记录所有可能组成的和
for (int n : nums) {
sum.add(n + number);
}
nums.add(number);
}
// sum中储存了所有加入数字可能组成的和，每次find只花费 O(1) 的时间在集合中判断一下是否存在即可
// 适合频繁使用find的场景
public boolean find(int value) {
return sum.contains(value);
}
- 小结
对于 TwoSum 问题，一个难点就是给的数组无序。对于一个无序的数组，似乎没什么技巧，只能暴力穷举所有可能。
一般情况下，我们会首先把数组排序再考虑双指针技巧。
另外，HashMap 或 HashSet 也可以辅助处理无序数组相关的简单问题。
1.2.3 反转数组
/**
* 反转数组
* <p>
* 反转一个char[]类型的字符数组
*/
private void reverseString(char[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// 交换 arr[left] 和 arr[right]
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
2. 数组删除、去重
对于数组来说，在尾部插入、删除元素是比较高效的，时间复杂度是 O(1)，但若在中间或开头插入、删除元素，就会涉及数据的搬移，时间复杂度为 O(N)，效率较低。
使用上面介绍的双指针技巧中的快慢指针技巧，也可避免直接删除数组中的元素，降低算法的复杂度。
2.1 有序数组/链表去重
- 有序数组去重
/**
* 有序数组去重
* <p>
* 删除排序数组中的重复项：如给定数组[1,1,2]，返回新的的长度2，原数组被修改为[1,2]
* 要求：原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度
* <p>
* 让慢指针slow走在后面，快指针fast走在前面探路，找到一个不重复的元素就告诉slow并让slow前进一步。
* 这样当fast指针遍历完整个数组nums后，nums[0..slow]就是不重复元素
*/
private int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
- 有序链表去重
有序链表去重和有序数组去重的区别是把数组赋值操作变成操作指针而已：
/**
* 有序链表去重
*/
private ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
2.2 移除元素
/**
* 移除元素
* <p>
* 给一个数组 nums 和一个值 val，需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度
* 如：给定 nums=[3,2,2,3], val=3，返回新的长度2，原数组修改为[2,2]
* 给定 nums=[0,1,2,2,3,0,4,2], val=2，返回新长度5，原数组修改为[0,1,3,0,4]
* <p>
* 如果fast遇到需要去除的元素，则直接跳过，否则就告诉slow指针，并让slow前进一步
*/
private int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
// 注意这里和有序数组去重的解法有一个重要不同，我们这里是先给nums[slow]赋值然后再给slow++，
// 这样可以保证nums[0..slow-1]是不包含值为val的元素的，最后的结果数组长度就是slow
slow++;
}
fast++;
}
return slow;
}
2.3 移动零
/**
* 移动零
* <p>
* 给你输入一个数组nums，原地修改，将数组中的所有值为 0 的元素移到数组末尾
* 如：nums = [0,1,4,0,2] ，会改成 [1,4,2,0,0]
* <p>
* 将所有 0 移到最后，其实就相当于移除nums中的所有 0，然后再把后面的元素都赋值为 0 即可。
*/
private void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0
// 返回去除 0 之后的数组长度
int p = removeElement(nums, 0);
// 将 p 之后的所有元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
总结：双指针技巧分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。数组「原地修改」的算法问题，其实核心也是快慢指针技巧。
参考链接：
