算法基础之双指针学习笔记

博主： JIeJaitt
发布时间：2020 年 07 月 15 日
158 次浏览
暂无评论
3036字数
分类：算法竞赛

双指针算法是一类常用且强大的算法技巧，它在解决各种问题时展现出了巨大的潜力。通过同时使用两个指针在不同位置上移动，双指针算法能够以高效的方式解决许多复杂的计算问题。

在双指针算法中，我们通常使用两个指针分别指向数组、字符串或链表的不同位置。这两个指针可以向相同方向移动，也可以向相反方向移动，具体取决于问题的要求。通过灵活地调整指针的移动方式，我们可以在不使用额外空间的情况下，以线性时间复杂度解决许多问题。

双指针算法的一个常见应用是在已排序的数组或链表中查找目标元素或满足特定条件的元素。通过将一个指针指向数组的起始位置，另一个指针指向数组的末尾位置，我们可以根据当前指针所指向的元素与目标元素的大小关系，逐步缩小搜索范围，从而快速找到目标元素。

双指针算法还可以用于解决数组中的重复元素问题。通过将一个指针指向当前元素，另一个指针指向下一个不同的元素，我们可以在原地删除重复元素，并返回不重复元素的个数。这种方法在空间复杂度要求较高的情况下尤为有用。

除了上述应用，双指针算法还可以用于解决数组的子数组或子序列问题、回文判断问题、两数之和问题等。通过合理地选择指针的起始位置和移动方式，我们可以在不增加额外空间复杂度的情况下，以较低的时间复杂度解决这些问题。

总之，双指针算法是一种强大的算法技巧，可以在许多问题中发挥重要作用。通过灵活运用双指针的移动方式和起始位置，我们可以高效地解决各种计算问题，提高算法的效率和性能。无论是在竞赛中还是在实际开发中，掌握双指针算法将为我们带来更多解决问题的可能性。

四数之和：给你一个由 `n` 个整数组成的数组 `nums` ，和一个目标值 `target` 。请你找出并返回满足`nums[a] + nums[b] + nums[c] + nums[d] == target`且**不重复**的四元组 `[nums[a], nums[b], nums[c], nums[d]]` （若两个四元组元素一一对应，则认为两个四元组重复）：可以按 **任意顺序** 返回答案 。

```bash
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
```

```bash
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
```

暴力四重循环，双指针可以优化一重循环。先枚举两个变量，然后后面两个变量的循环用双指针来优化，变成O(n)。在第三个循环同时使用两个指针遍历，将复杂度降为 $O(n^3)$，提前将数组排序，根据数组有序性以及一个位置只能出现一种数一次，去除重复解。因为数组提前排过序，如果当前值跟前面一个值相同的话，则可以跳过这些一定不会出现在解中的数。

总结该类问题：如果两个数的话直接双指针，如果三个数的话先枚举前面一个数再双指针；如果四个数的话先枚举前面两个数再双指针，如果有五个数就先枚举前面三个数，如果有n个数就涉及到动态规划背包了。

```cpp
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<nums.size();i++) {
            if (i && nums[i] == nums[i - 1]) continue;
            for(int j=i+1;j<nums.size();j++) {
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                for(int k=j+1,u=nums.size()-1;k<u;k++) {
                    if(k>j+1 && nums[k]==nums[k-1]) continue;
                    while( u-1>k && (long long )nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u --;
                    if ((long long)nums[i] + nums[j] + nums[k] + nums[u] == target) {
                        res.push_back({nums[i], nums[j], nums[k], nums[u]});
                    }
                }
            }
        }
        return res;
    }
};
```

```go
func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var res [][]int

for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

for j := i + 1; j < len(nums); j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

for k, u := j+1, len(nums)-1; k < u; k++ {
                if k > j+1 && nums[k] == nums[k-1] {
                    continue
                }

for u-1 > k && int64(nums[i])+int64(nums[j])+int64(nums[k])+int64(nums[u-1]) >= int64(target) {
                    u--
                }

if int64(nums[i])+int64(nums[j])+int64(nums[k])+int64(nums[u]) == int64(target) {
                    res = append(res, []int{nums[i], nums[j], nums[k], nums[u]})
                }
            }
        }
    }

return res
}
```

这个算法的时间复杂度为O(n^3)，其中n是输入数组nums的长度。这是因为算法使用了四层嵌套循环来遍历数组，并且每层循环的迭代次数都与n相关。

空间复杂度为O(1)，即常数空间。尽管算法使用了一个二维切片res来存储结果，但其空间占用与输入规模无关，因此可以视为空间复杂度为常数级别。

需要注意的是，这里的时间和空间复杂度分析是基于输入规模为n的情况下进行的。如果考虑到排序操作的时间复杂度，那么整体的时间复杂度将会是O(n^3 log n)，因为在算法中使用了sort.Ints对数组进行排序，其时间复杂度为O(n log n)。

最后修改：2023 年 08 月 31 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

算法基础之双指针学习笔记

JIeJaitt • 2020 年 07 月 15 日

```bash
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
```

```bash
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
```

```go
func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var res [][]int

for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

for j := i + 1; j < len(nums); j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

for k, u := j+1, len(nums)-1; k < u; k++ {
                if k > j+1 && nums[k] == nums[k-1] {
                    continue
                }

for u-1 > k && int64(nums[i])+int64(nums[j])+int64(nums[k])+int64(nums[u-1]) >= int64(target) {
                    u--
                }

return res
}
```

这个算法的时间复杂度为O(n^3)，其中n是输入数组nums的长度。这是因为算法使用了四层嵌套循环来遍历数组，并且每层循环的迭代次数都与n相关。

空间复杂度为O(1)，即常数空间。尽管算法使用了一个二维切片res来存储结果，但其空间占用与输入规模无关，因此可以视为空间复杂度为常数级别。

算法基础之双指针学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

欢迎使用 Typecho

团队项目管理 Git 与 GitHub 使用经验

流媒体视频点播网站 scheduler 调度器模块实现

算法基础之双指针学习笔记

Redis 缓存问题（图解：三种缓存问题）

ubuntu 升级 16.04 to 20.04

Go语言error标准库

scikit-learn简单了解

我两年的坚持，值了！

流媒体视频点播网站 scheduler 调度器模块实现

算法基础之双指针学习笔记

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

算法基础之双指针学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款