共计 9035 个字符，预计需要花费 23 分钟才能阅读完成。
数组 + 双指针
数组是一种简单的数据结构，是由相同类型的元素组成的数据集合，并且占据一块连续的内存空间，按照顺序存储数据。
双指针是一种常用的解题思路，可以使用两个相同或相反方向的指针扫描数组从而达到解题目的。
此处的指针非 C/C++里的指针类型，而是一个更加宽泛的概念，它是能够定位数据容器中某个数据的手段。一般是指数组下标。
一、原地修改数组元素题型
原地修改数组的题型一般都需要用到双指针。
LeetCode 26.删除有序数组中的重复项
给定一个有序数组，删除数组中重复元素，确保元素的相对位置不变，并返回删除后的数组长度。
输入：nums = [1,1,2]
输出：2, nums = [1,2]说明：修改数组后，方法返回修改后的数组长度 2，此时 nums 的长度仍然是 3。但是在进行评测时，只评测返回后的长度大小，超过部分忽略。
思路
首先数组是有序的，意味着如果存在重复元素，那么这些元素就是相邻的，若要删除这些重复元素，就需要将不重复的元素移动左边。
我们声明一个指针left，该指针始终指向左边非重复项最后一个元素，同时再声明一个指针right,该指针用于找到和 left 指向的元素不相同的元素。
当left和right两个指针指向的元素相同，则让 right 继续向右移动，直到找到不相同的元素。
当left和right两个指针指向的元素不同时，先让 left+1，再将当前 left 的元素赋上 right 指向的元素即可。
当right等于 len 时，非重复项的有序数组长度就是left+1。
代码
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int len = nums.length;
int l = 0, r=1; // r=0 也行，此时肯定会执行一次r++
while(r < len){
if(nums[l] == nums[r]){
r++;
}else{
l++;
nums[l] = nums[r];
}
}
return l + 1;
}
}时空复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
LeetCode 27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]说明：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
思路
本题和上题一样，原地删除数组中指定元素val，返回删除后的数组长度，评测时评测返回长度内的元素范围。因此，我们只需要将数组中非val的值放在左边即可。
声明一个指针left，该指针始终指向不包含val的子数组末尾+1；同时再声明一个指针right，该指针会不断向右找到非val的值。
当right指向的元素是val值时，让 right+1 即可，因为right指针的目的是找到非val元素；
当right指向的元素为非val值时，将 right 指向的元素赋值到 left 指向的元素上，right 和 left 同时加 1。
当 right 等于 len 时，寻找结束，此时left就是数组长度。
代码
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
int left = 0, right = 0;
while(right < len){
// if(nums[right] == val){
// right++;
// }else{
// nums[left] = nums[right];
// left++;
// right++;
// }
// 上述部分可简写成下面的代码
if(nums[right] != val){
nums[left] = nums[right];
left++;
}
right++;
}
return left;
}
}时空复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
我们可以发现上面两道例题都是通过定1寻1的方式来完成数组修改的。两个指针中，一个指针负责找到操作位，另外一个指针负责找到操作元素，当无操作元素时，跳出，程序执行完毕。
下面将介绍另外一种齐头并进的方式，该方式本质上和定1寻1并无本质区别，只是它们实现的代码会给人一种齐头并进的感觉.
LeetCode 905.按奇偶排序数组
给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
输入：nums = [3,1,2,4]
输出：[2,4,3,1]说明：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
思路
题目的大概意思就是：给定一个数组，将数组中的偶数放在左边，奇数放在右边。因为题目对空间大小没有要求，因此我们很容易想到一种实现方式：开辟一个同样大小的空数组和两个指针，一个指向头部，另外一个指向尾部，然后遍历数组，依次赋值就行。时空复杂度均为：O(n)。
那如何只用O(1)的空间复杂度实现同样的效果呢？很明显我们只能在原数组上进行修改。
因为题目要求偶数在左，奇数在右，因此我们可以声明两个指针left和right，让这两个指针分别指向数组的头部和尾部。然后在left < right的情况下，我们一起移动两指针，直到left指向奇数元素，right指向偶数元素，然后交换两指针指向的元素，重复此步骤，就能得到左偶右奇了。
代码
class Solution {
public int[] sortArrayByParity(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int len = nums.length;
int left = 0, right = len - 1;
while(left < right){
// 找到左边为奇数的元素
while(left < len && nums[left]%2==0)left++;
// 找到右边为偶数的元素
while(right > -1 && nums[right]%2==1) right--;
// 交换两个元素
if(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
}时空复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
LeetCode 922.按奇偶排序数组 II
给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。
对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
你可以返回 任何满足上述条件的数组作为答案 。
输入：nums = [4,2,5,7]
输出：[4,5,2,7]说明：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
思路
对于非负整数数组，题目要求当下标 i 为奇数时，下标 i 对应的元素 nums[i]也必须时奇数;当 i 为偶数时，nums[i]也是偶数。也就是说对于数组中的每个元素 nums[i],满足：nums[i] % 2 == i % 2。
如何保证上述条件成立呢？我们只需要定义两个指针p1和p2,这两个指针分别指向奇数位和偶数位下标，在p1 < len && p2 < len 的情况下，同时移动p1和p2指针，当p1指向偶数，p2指向奇数时，交换两指针指向的元素，重复上述步骤。
代码
class Solution {
public int[] sortArrayByParityII(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int len = nums.length;
int p1 = 0, p2 = 1; // p1指向偶数，p2指向奇数
while(p1 < len && p2 < len){
// 先找到偶数位为奇数的位置
while(p1 < len && nums[p1] % 2 == p1 % 2) p1 += 2;
// 再找到奇数位为偶数的位置
while(p2 < len && nums[p2] % 2 == p2 % 2) p2 += 2;
// 调换两个位置
if(p1 < len && p2 < len){
int t = nums[p1];
nums[p1] = nums[p2];
nums[p2] = t;
}
}
return nums;
}
}二、有序数组中的两数之和问题
双指针除了能够让我们对数组进行简单的原地修改外，我们还可以在时空复杂度分别为:O(n)和O(1)的情况下找到有序数组中两元素之和等于 target 的元素下标p1和p2。
LCR 006. 两数之和 II - 输入有序数组
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]说明：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
思路
这道题可以通过非常暴力手段进行求解，就是先固定一个数字 nums[i],在从 i 往后依次遍历数组另外一个数字 nums[j],如果nums[i]+nums[j] == k,则找到了。时空复杂度分别为 O($n^2$)和 O(1)。
除此之外，我们还可以对上面的暴力解法进行优化：固定一个数字 nums[i]后，另外一个数字通过二分查找算法来查找target-nums[i]。时空复杂度分别为 O($nlogn$)和 O(1)。
另外，我们也可以采用空间换时间手段将时间复杂度降低至 O(n)：创建一个哈希表 map，key 为target-nums[i]，value 为i,每次遍历 nums 时，先判断 map 中是否存在target-nums[i]的值，如果存在，返回：[map.get(target-nums[i]),i]，否则向 map 中添加：map.put(nums[i],i)。时空复杂度均为:O(n)，代码如下：
代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length == 0) return new int[]{-1,-1};
int len = numbers.length;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<len;i++){
if(map.containsKey(target-numbers[i])){
return new int[]{map.get(target-numbers[i]),i};
}
map.put(numbers[i],i);
}
return new int[]{-1,-1};
}
} 上面的算法仍然没有达到最优的时空效率，我们可以使用双指针的技巧来让时空效率分别达到 O(n)和 O(1)。做法是：定义两个指针 p1 和 p2，分别指向数组头部和尾部，由于数组是有序的，因此当nums[p1]+nums[p2] < target时，意味着左边小了，因此我们可以让p1+1；当nums[p1] + nums[p2] > target时，意味着右边大了，因此我们可以让p2-1，如此往复，直到两指针相遇退出或两指针指向的元素之和等于 targte 时，返回[p1,p2]。
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length == 0) return new int[]{-1,-1};
int len = numbers.length;
int p1 = 0, p2 = len - 1;
while(p1 < p2){
int sum = numbers[p1] + numbers[p2];
if(sum > target){
p2--;
}else if(sum < target){
p1++;
}else{
return new int[]{p1,p2};
}
}
return new int[]{-1,-1};
}
}LeetCode 35.三数之和
本题可视为是两数之和的进阶。
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]说明：
- nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
- nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
- nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
- 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
- 注意，输出的顺序和三元组的顺序并不重要。
思路
这道题对于会两数之和的人来说非常简单，三个数字，我们确定一个nums[i],然后在[i,n-1]的区间里寻找两数之和等于-nums[i]，如果存在这两个数，说明找到了一个三元组。现在需要解决的是，如何对三元组进行去重，这其实也很简单。当找到一个三元组[nums[i],nums[j],nums[k]]时，跳过所有相同的值就能过滤掉重复的三元组，这也就意味着，我们需要对数组进行排序，因为只有排序后的数组，相同元素彼此相邻。
代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums == null || nums.length == 0) return new LinkedList<>();
int len = nums.length;
List<List<Integer>> result = new LinkedList<>();
Arrays.sort(nums);
// 先固定nums[i]，然后在[i+1,n-1]的区间里找到两数之和等于-nums[i]的下标
for(int i=0; i<len-2;){
twoSum(nums, i, result);
int temp = nums[i];
// 跳过nums[i]的重复值
while(i<len&&nums[i] == temp) i++;
}
return result;
}
// 求解两数之和
private void twoSum(int[] nums, int i, List<List<Integer>> result){
int len = nums.length;
int left = i+1, right = len - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
result.add(List.of(nums[i],nums[left],nums[right]));
int temp = nums[left];
while(left < len && nums[left] == temp) left++;
}else if(sum > 0){
right--;
}else{
left++;
}
}
}
}三、无序数组的子数组问题
上面主要讨论了在有序数组中，使用双指针可以在 O(n)和 O(1)的时空复杂度下求解数组中两元素之和等于 target 的两元素下标，那么在无序数组中，双指针又能干嘛呢？
无序数组中双指针的经典运用就是滑动窗口。我们使用两个指针p1和p2维护着数组中的一段子区间，这就构成了一个窗口。通过移动两指针，保证该窗口内的元素满足某个特性，当移动到末尾时，程序结束得到结果。
LeetCode 643.子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 $10^{-5}$ 的答案都将被视为正确答案。
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
思路
本题可以简单表述为：求给定数组的指定长度 k 的子数组最大平均数。需要注意的是：最大平均数 = 最大元素之和 / k。因此本题本质上是让我们求指定长度 k 的最大元素之和。因此，我们可以使用滑动窗口手段，使用两指针p1和p2，这两个指针共同构成了一个窗口。
移动 p2,当p2 - p1 + 1 == k时，说明窗口长度为 k，此时计算窗口内的所有元素之和。计算元素之和我们不需要通过遍历，只需要定义一个变量sum，当 p2 元素滑入窗口时，sum += nums[p2]即可，当 p1 元素滑出窗口时，sum -= nums[p1]，这样 sum 就始终是窗口内元素之和了。
当窗口长度为 k，并计算出元素之和后，我们就能求解最大元素之和maxSum，同时，p1 ++;,让 p1 所在元素滑出窗口。
当 p2 到达末尾时，程序结束，我们就能得到最大子数组元素之和 maxSum 了,返回时，返回maxSum / k * 1.0即可。
代码
class Solution {
public double findMaxAverage(int[] nums, int k) {
if(nums == null || nums.length == 0 || nums.length < k) return 0;
int len = nums.length, p1 = 0, maxSum = Integer.MIN_VALUE, sum = 0;
for(int p2 = 0; p2 < len; p2 ++){
sum += nums[p2];
// 当窗口长度为k
if(p2 - p1 + 1 == k){
// 计算最大和
maxSum = Math.max(sum, maxSum);
// p1所在元素滑出
sum -= nums[p1++];
}
}
return maxSum / (k * 1.0);
}
}上述入门例题告诉我们设计一个滑动窗口我们需要考虑以下几点：
- 右边元素（p2 指针）什么条件下滑入？
- 左边元素（p1 指针）什么条件下滑出？
- 窗口内的所有元素能带给我们什么性质？
带着上面三个问题，我们不妨再试试下面的例题
LeetCode 713.乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
输入：nums = [10,5,2,6], k = 100
输出：8解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
思路
本题的求解方向非常明确，让我们求解子数组乘积小于 k 的数量。现在假设一段子数组[p1,p2]内的元素之积小于 k，那么[p1,p2]内乘积小于 k 的子数组数量有多少呢？
对于乘积小于 k 的子数组[p1,p2],p2 是固定不动的,因此[p1+1,p2],[p1+2,p2],...,[p1 + n, p2]均是小于 k 的子数组，而个数就是p2 - p1 + 1。因此，每当我们找到乘积小于 k 的子数组[p1,p2]时，将p2-p1+1进行累加即可求出子数组之和。
代码
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
int p1 = 0, len = nums.length, mul = 1,res = 0;
for(int p2 = 0; p2 < len; p2++){
mul *= nums[p2];
// 滑出条件：窗口内的元素之积>=k时
while(p1 <= p2 && mul >= k){
mul /= nums[p1++];
}
// 此时窗口内的元素之积一定小于k
res += p2 - p1 + 1;
}
return res;
}
}LeetCode 2461.长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
- 子数组的长度是 k，且
- 子数组中的所有元素 各不相同 。
- 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
思路
本题给我们的滑动窗口添加了一个限制：元素不能重复。我们首先想到使用用哈希表，因为哈希表本身就具有去重功能，因此，我们将滑动窗口里的元素放在哈希表中即可。
代码
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0 || nums.length < k) return 0;
int p1 = 0, len = nums.length;
long ans=0, sum = 0;
Set<Integer> set = new HashSet<>();
for(int p2 = 0;p2<len;p2++){
// 如果滑入的元素p1已经存在了，那么将p1元素移出，直到set中不存在p2元素
while(set.contains(nums[p2])){
set.remove(nums[p1]);
sum -= nums[p1++];
}
// sum是窗口中元素的和
sum += nums[p2];
set.add(nums[p2]);
// 当长度为k时，计算最大和
if(p2 - p1 + 1 == k){
ans = Math.max(ans, sum);
sum -= nums[p1];
set.remove(nums[p1++]);
}
}
return ans;
}
}总结
- 原地修改数组元素；
- 数组有序，找两数之和问题；
- 数组无序，元素均是正数，可求解具有某个性质的子数组；
