【LeetCode】数组——双指针法

码农世界 2024-05-23 后端 67 次浏览 0个评论

1 双指针法

1.1 介绍

双指针法是一种常用的算法技巧，通常用于处理数组或链表中的问题。它使用两个指针，通常一个从数组的开始位置遍历，另一个从数组的末尾位置开始遍历，根据问题的不同，这两个指针可以同时移动，也可以根据条件移动。

1.2 使用场景

双指针法可以用于多种场景，如：

1.数组合并：将两个有序数组合并为一个有序数组。
2.链表操作：如判断链表是否有环、寻找链表的中点等。
3.数组操作：如寻找数组中的两数之和等于特定值的两个数。
4.滑动窗口：用于解决数组或字符串的子串问题。

2 LeetCode相关题解

2.1 27. 移除元素

27.移除元素链接

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：一个指针（fast）用来寻找不等于val的元素，另一个指针（slow）将这个元素添加到数组中。
```
int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    int fast = 0;
    for(; fast < numsSize; fast++)
    {
        if(nums[fast] != val)
        {
            nums[slow] = nums[fast];
            slow++;
        }
        else 
            continue;
    }
    return slow;
}
```
2.2 26.删除有序数组中的重复项

26.删除有序数组中的重复项链接

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 1：

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

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按非严格递增排列

思路：一个指针（fast）用来寻找新数组（不包含相同元素的数组）中的元素，另一个指针（slow）用来将该元素添加到新数组中。
```
int removeDuplicates(int* nums, int numsSize) {
    int slow = 0;
    int fast = 0;
    for(;fast < numsSize; fast++)
    {
        if(nums[slow] != nums[fast])
        {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow+1;
}
```
2.3 283.移动零

283.移动零链接

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

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

示例 1:

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

示例 2:

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

思路：先使用双指针法将非零元素前移，再将后面的元素赋值为零。
```
void moveZeroes(int* nums, int numsSize) {
    int slow = 0;
    int fast = 0;
    for(; fast < numsSize; fast++)
    {
        if(nums[fast] != 0)
            nums[slow++] = nums[fast];
    }
    for(; slow < numsSize; slow++)
    {
        nums[slow] = 0;
    }
}
```
2.4 844.比较含退格的字符串

844.比较含退格的字符串链接

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

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

示例 1：

输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

示例 2：

输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”。

示例 3：

输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 ‘#’

思路：分别计算出两个字符串最终输出的字符串，再进行对比。
```
#include 
char* build(char* s, int len){
    int j = 0;
    char* arr = (char*)malloc((len+1) * sizeof(char));
    if(arr == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    for(int i=0;i < len; i++){
        if(s[i] == '#'){
            if (j > 0) {
                j--;
            }
        }
        else {
            arr[j++] = s[i];
        }
    }
    arr[j] = '\0';
    return arr;
}
bool backspaceCompare(char * s, char * t){
    char* c1 = build(s,strlen(s));
    char* c2 = build(t,strlen(t));
    if (strcmp(c1, c2) == 0) {
        return true;
    }
    return false;
}
```
2.5 977.有序数组的平方

977.有序数组的平方链接

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按非递减顺序排序

思路：数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。利用双指针法，从两边开始向中间遍历，比较两边元素平方的大小，大的放到新数组中。
```
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* ret = (int*)malloc(sizeof(int) *numsSize);
    int fast = numsSize - 1;
    int slow = 0;
    int i = numsSize - 1;
    while(slow <= fast)
    {
        if(nums[slow]*nums[slow] > nums[fast]*nums[fast])
        {
            ret[i] = nums[slow]*nums[slow];
            slow++;
            i--;
        }
        else 
        {
            ret[i] = nums[fast]*nums[fast];
            fast--;
            i--;
        }
    }
    return ret;
}
```
如果在 while(slow <= fast) 改为 while(slow < fast)，会漏了 slow == fast 的这个元素。

2.6 209.长度最小的子数组

209.长度最小的子数组链接

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
```
int minSubArrayLen(int target, int* nums, int numsSize) {
    int left = 0;
    int right = 0;
    int sum = 0;
    int lenth = 0;
    int retlenth = numsSize + 1;
    for(; right < numsSize; right++)
    {
        sum += nums[right];
        while(sum >= target)
        {
            lenth = right - left + 1;
            retlenth = retlenth < lenth?retlenth : lenth;
            sum -= nums[left++];
        }
    }
    if(retlenth == numsSize + 1) return 0;
    return retlenth;
}
```
- 关于 retlenth = numsSize + 1 的设定：
  - 排除了将数组全加起来仍然小于target的情况；如[1,1,1,1,1] 15。
  - 同时也能返回将数组全加起来恰好等于target的情况；如[1,2,3,4,5] 15。
  - 关于 while(sum >= target) 使用 while 循环而不是 if ：
    - 如果使用的是if，那么后面的代码只执行一次，但你并不能判断将起始位置（left）后移过的 sum 一定比 target 小