算法训练之 -- 双指针

双指针

1. 思路

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

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

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。27. 移除元素 - 力扣（LeetCode）

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针：寻找新数组的元素，新数组就是不含有目标元素的数组。这个指针需要一直向前，同时寻找目标元素。
慢指针：指向更新新数组下标的位置。指向需要更新的元素位置，如果没有找到目标元素，则跟着快指针一起向前移动。

2. 解法

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slowIdx, fastIdx = 0, 0
        for fastIdx in range(len(nums)):
            if nums[fastIdx] != val:		# 快指针寻找目标元素，并一直向前移动，直接满足结束条件
                nums[slowIdx] = nums[fastIdx]	# 慢指针指向需要更新的元素位置，如果找到目标元素，则跟着快指针向前移动
                slowIdx += 1
        return slowIdx

C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIdx = 0, fastIdx = 0;
        for(fastIdx=0; fastIdx<nums.size(); fastIdx++){
            if(nums[fastIdx] != val)
                nums[slowIdx++] = nums[fastIdx];
        }
        return slowIdx;
    }
};

3. 变种

(1) 题目： 给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。26. 删除有序数组中的重复项 - 力扣（LeetCode）

思路：还是使用常规的双指针解法。关键步骤是找到一个判断语句，使得 slow 慢指针移动，不同的题目 slow 移动的条件不同，只要找到符合移动的条件，就可以直接进行逻辑上的元素移动覆盖。最后返回 slow + 1 即为最后的数组的长度。
PS：一般情况下快指针是随着循环一直移动的。

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        for fast in range(len(nums)):
            if nums[slow] != nums[fast]:  # 判断slow指针移动的语句
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1						# 返回最终的数组长度

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 0;
        for(fast = 0; fast < nums.size(); fast++){
            if(nums[slow] != nums[fast]){
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

⁕⁕ (2) 题目：给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。844. 比较含退格的字符串 - 力扣（LeetCode）

思路： 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；若该字符为普通字符：
若skip 为 0，则说明当前字符不需要删去；
若skip 不为 0，则说明当前字符需要删去，我们让skip 减 1。
PS：双指针移动，不一定两个指针都在同一个数组上，也可以在两个不同的数组上。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) -1, len(t) - 1	# 从后往前
        skipS = skipT = 0
        while i>=0 or j>=0:
            while i>=0:
                if s[i] == "#":	# 如果遇到了 ‘#’， 则说明需要跳过这个字符
                    skipS += 1
                    i -= 1			# i 指针需要一直移动
                elif skipS > 0:	# 如果还存有‘#’， 则需要将 ‘#’号前面的字符给消除掉
                    skipS -= 1
                    i -= 1
                else:
                    break
            while j>=0:
                if t[j] == "#":
                    skipT += 1
                    j -= 1
                elif skipT > 0:
                    skipT -= 1
                    j -= 1
                else:
                    break
            if i>=0 and j>= 0:
                if s[i] != t[j]:
                    return False
            elif i>=0 or j>=0:
                return False

            i -= 1
            j -= 1

        return True

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while(i >= 0 || j >=0){
            while(i>=0){
                if(s[i--] == '#')
                    skipS += 1;
                else if(skipS > 0){
                    skipS--;
                    i--;
                }
                else break;
            }
            while(j>=0){
                if(t[j--] == '#')
                    skipT += 1;
                else if(skipT > 0){
                    skipS--;
                    j--;
                }
                else break;
            }

            if(i>=0 && j>=0){
                if(s[i] != t[j])
                    return false;
            }
            else if(i >=0 || j >= 0)
                return false;
            i--;
            j--;
        }
        return true;
    }
};

(3) 题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。977. 有序数组的平方 - 力扣（LeetCode）

思路：
使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。
找到正数和负数的分界线，两个指针分别指向分界线和分界线的后一位，然后从中间往两端进行比较，将较小的放入新的数组中。

Python

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n

        i, j, idx = 0, n-1, n-1
        while i<=j:
            if nums[i]**2 > nums[j]**2:
                ans[idx] = nums[i]**2
                i += 1
            else:
                ans[idx] = nums[j]**2
                j -= 1
            idx -= 1
        
        return ans

C++

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i=0, j=nums.size()-1, idx=nums.size()-1;
        vector<int> ans(nums.size());
        while(i<=j){
            if(nums[i]*nums[i] > nums[j]*nums[j]){
                ans[idx--] = nums[i] * nums[i];
                i++;
            }else{
                ans[idx--] = nums[j] * nums[j];
                j--;
            }
        }
        return ans;
    }
};

⁕⁕ (4) 题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。11. 盛最多水的容器 - 力扣（LeetCode）

思路：面对这个题目，如果没有经验，很难想到双指针。本题的容量大小，即为短板 * 当前水槽的长度 。设两指针 i , j ，指向的水槽板高度分别为h[i], h[j] ，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下面积公式：\[S(i,j)=min(h[i],h[j])×(j−i)\]
同时，无论长板还是短板向中间收窄一格，都会导致水槽底边宽度 -1：
若向内移动短板，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大。
若向内移动长板，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小。
PS：为了减少时间，进行一下优化，当水槽的容量大小，大于max(height) * (j - i)时，则说明，水槽的容量不会再有机会变大了。

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = len(height)
        left, right = 0, l - 1
        ans = 0
        maxh = max(height) # 最大的 高度
        while left <= right:
            if height[left] < height[right]:
                ans = max(ans, height[left] * (right-left))
                left += 1
            else:
                ans = max(ans, height[right] * (right-left))
                right -= 1
            if ans >= maxh * (right - left): # 优化
                break
        return ans

C++

// 因为C++的vector容器需要添加算法头文件才能 使用max_element()函数
class Solution { 
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ans = 0;
        while(left <= right){
            if(height[left] < height[right]){
                ans = max(ans, (right - left) * height[left++]);
            }else{
                ans = max(ans, (right - left) * height[right--]);
            }
        }
        return ans;
    }
};

(5) 题目：给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。16. 最接近的三数之和 - 力扣（LeetCode）

思路：
首先进行数组排序，时间复杂度 O(nlogn)
在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans
同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end--，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果
整个遍历过程，固定值为 n 次，双指针为 n 次，时间复杂度为 O(n2)
总时间复杂度：O(nlogn)+O(n2)=O(n2)

Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        ans = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)):
            l, r = i + 1, len(nums) - 1
            while l < r:			# 注意不需要等号
                s = nums[l]+nums[r]+nums[i]
                if abs(target - s) < abs(target - ans):
                    ans = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return ans
        return ans

C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans =  nums[0] + nums[1] + nums[2];
        for(int i=0; i<nums.size(); i++){
            int l = i + 1, r = nums.size() - 1;
            while(l < r){		// 注意不需要等号
                int sum = nums[i] + nums[l] + nums[r];
                if(abs(target - sum) < abs(target - ans))
                    ans = sum;
                if(sum < target)
                    l++;
                else if(sum > target)
                    r--;
                else return ans;
            }
        }
        return ans;
    }
};

算法

#刷题

算法训练之 -- 双指针

http://seulqxq.top/posts/3463/

作者

SeulQxQ

发布于

2023年12月12日

许可协议

TensoRF - Tensorial Radiance Fields 上一篇

STL源码剖析下一篇