Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/AMS-Regular.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【LeetCode刷题】:双指针篇(三数之和,四数之和)

【LeetCode刷题】:双指针篇(三数之和,四数之和)

作者头像
爱喝兽奶的熊孩子
发布于 2025-01-22 01:54:41
发布于 2025-01-22 01:54:41
14310
代码可运行
举报
文章被收录于专栏:C语言基础C语言基础
运行总次数:0
代码可运行

一、三数之和

1. 题目解析

三数之和【点击跳转】

题目的意思是给了我们一个数组nums,让我们找出三个下标不相同的数nums[i],nums[j],nums[k],要求这三个数的和恰好等于,然后返回这三个数

注意: 返回的这个三元组不能是重复的 我们可以结合示例1的解释来看:

示例 1:

输入的数组是nums = [-1, 0, 1, 2, -1, -4]

解释:

可以看到第一种和第二种三元组里的元素都是 [-1, 0, 1] 忽略掉元素的顺序,他们的元素是一样的,所以是同一个三元组,所以这两个中任选一个就行了,另外,三元组中元素的顺序不重要,可以随意。所以输出的结果就是 [-1, 0, 1] 和 [-1, -1, 2]

2. 讲解算法原理

解法一:排序 + 暴力枚举 + 容器去重 我们可以将所有符合要求的三元组给枚举出来,然后直接利用set容器去重,但是在示例中可能会有很多种像示例一中的这种情况,所以我们可以先给数组排个序,另外,排完序后我们得到的三元组里面的元素顺序也会得到固定,这样也能够更好的让我们利用容器去重。

时间复杂度为:

这里就直接给代码了,最后的提交结果肯定是超时的。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> hash;
        int n = nums.size();
        vector<vector<int>> ret;
        // 排序
        sort(nums.begin(), nums.end());
        // 暴力枚举
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                for(int k = j + 1; k < n; k++)
                {
                    if(nums[i] + nums[j] + nums[k] == 0)
                    {
                        vector<int> tmp = {nums[i], nums[j], nums[k]};
                        // 容器去重  --> 排好序后元素位置固定, 相同的两个三元组第一个元素和最后一个元素肯定是相同的
                        if(hash.find(tmp) == hash.end())
                        {
                            ret.push_back(tmp);
                            hash.insert(tmp);
                        }
                    }
                }
            }
        }
        return ret;
    }
};

解法二:排序 + 双指针 在暴力枚举的基础上进行的优化,前面做过一道和为s的两个数,如果想到这题,那么三数之和这道题就很好优化。 我们可以先固定一个数,假设这个数的下标是i,那么我们就在数组[i + 1, n - 1](n表示这个数组的长度)这个区间做那个和为s的两个数,只不过这两个数的和是等于nums[i]的相反数。

注意: 1、跟和为s的两个数不同的是,这里不止有一种结果,所以利用双指针找到一组结果后,不要挺,需要缩小范围然后继续找,确保结果没有遗漏。 2、另外一个就是去重问题,首先想到的就是利用容器的特性去重。还有就是找到一种结果之后,可以让指针跳过重复的元素进行去重。

这里需要注意一下指针越界的问题,题目中给定的数组nums可能是 [0, 0, 0, 0, 0],这种情况下指针会越界,所以在判断重复的元素时,left和right指针的关系是left < right,i 的话则需要小于数组的长度。

3. 代码编写

C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        // 排序
        sort(nums.begin(), nums.end());
        // 利用双指针解决问题
        for(int i = 0; i < n;  )
        {
            // 小优化
            if(nums[i] > 0)  break;
            // 定义左右双指针
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right)
            {
                // 求和
                int sum = nums[left] + nums[right];
                if(sum < target) left++;
                else if(sum > target)  right--;
                else
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    // 继续移动指针, 确保不漏
                    left++, right--;
                    // 去重left 和 right + 防止越界
                    while(left < right && nums[left] == nums[left - 1])  left++;
                    while(left < right && nums[right] == nums[right + 1])  right--;
                }
            }
            // 去重固定的数 i + 防止越界
            i++;
            while(i < n && nums[i] == nums[i - 1])  i++;
        }
        // 返回结果
        return ret;
    }
};

C语言代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 比较函数,用于qsort排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    if (nums == NULL || numsSize < 3 || returnSize == NULL || returnColumnSizes == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    qsort(nums, numsSize, sizeof(int), compare);

    *returnSize = 0;
    int capacity = numsSize / 3; // 合理的初始大小
    int** ret = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));

    for (int i = 0; i < numsSize - 2; ) {
        if (nums[i] > 0) break;

        int left = i + 1, right = numsSize - 1, target = -nums[i];
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                if (*returnSize >= capacity) {
                    capacity *= 2; // 动态扩展
                    int** temp = (int**)realloc(ret, capacity * sizeof(int*));
                    if (temp == NULL) {
                        free(ret);
                        free(*returnColumnSizes);
                        *returnSize = 0;
                        *returnColumnSizes = NULL;
                        return NULL;
                    }
                    ret = temp;
                    *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
                }

                ret[*returnSize] = (int*)malloc(3 * sizeof(int));
                ret[*returnSize][0] = nums[i];
                ret[*returnSize][1] = nums[left];
                ret[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;

                left++, right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            }
        }

        i++;
        while (i < numsSize && nums[i] == nums[i - 1]) i++;
    }

    ret = (int**)realloc(ret, *returnSize * sizeof(int*));
    *returnColumnSizes = (int*)realloc(*returnColumnSizes, *returnSize * sizeof(int));
    return ret;
}

Python代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 对数组进行排序
        n = len(nums)
        ret = []  # 用于存储结果的列表

        for i in range(n):
            # 小优化:如果当前数字大于0,则后续数字也大于0,不可能组成和为0的三元组
            if nums[i] > 0:
                break

            # 去重:如果当前数字与前一个数字相同,跳过
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 定义左右双指针
            left, right = i + 1, n - 1
            target = -nums[i]

            while left < right:
                total = nums[left] + nums[right]

                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    # 找到一个满足条件的三元组
                    ret.append([nums[i], nums[left], nums[right]])

                    # 移动指针并去重
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return ret
二、四数之和
1. 题目解析

四数之和【点击跳转】

和三数之和的题目意思一模一样,只不过是由三个数的和等于0变成了数组中四个数相加要等于目标值target,符合要求的四元组不能重复,结果不能有遗漏。

2. 讲解算法原理

你在逗我呢?三数之和都会了,四数之和还不会?不准往下看了,赶紧给我写代码去OvO。

解法一:排序 + 暴力枚举 + 容器去重 我们可以将所有符合要求的四元组给枚举出来,然后直接利用set容器去重,但是在示例中可能会有很多种像示例一中的这种情况,所以我们可以先给数组排个序,另外,排完序后我们得到的四元组里面的元素顺序也会得到固定,这样也能够更好的让我们利用容器去重。

时间复杂度为:

这里就直接给代码了,最后的提交结果肯定是超时的。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>> hash;
        int n = nums.size();
        vector<vector<int>> ret;
        // 排序
        sort(nums.begin(), nums.end());
        // 暴力枚举
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                for(int k = j + 1; k < n; k++)
                {
                    for(int y = k + 1; y < n; y++)
                    {
                        if((long long)nums[i] + nums[j] + nums[k] + nums[y] == target)
                        {
                            vector<int> tmp = {nums[i], nums[j], nums[k], nums[y]};
                            // 容器去重  --> 排好序后元素位置固定, 相同的两个三元组第一个元素和最后一个元素肯定是相同的
                            if(hash.find(tmp) == hash.end())
                            {
                                ret.push_back(tmp);
                                hash.insert(tmp);
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};

解法二:排序 + 双指针 其实就和三数之和的算法原理是一模一样的。只不过是由固定一个数变成了固定两个数,先固定一个数,然后对后面的数使用三数求和即可。

在暴力枚举的基础上进行的优化,前面做过一道和为s的两个数,如果想到这题,那么四数之和这道题就很好优化。 我们可以先固定一个数,假设这个数的下标是i,那么我们就在数组[i + 1, n - 1](n表示这个数组的长度)这个区间做那个和为s的两个数,只不过这两个数的和是等于nums[i]的相反数。

注意: 1、跟和为s的两个数不同的是,这里不止有一种结果,所以利用双指针找到一组结果后,不要挺,需要缩小范围然后继续找,确保结果没有遗漏。 2、另外一个就是去重问题,首先想到的就是利用容器的特性去重。还有就是找到一种结果之后,可以让指针跳过重复的元素进行去重。

3. 代码编写

C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // if(n < 4)  return ret;
        for(int i = 0; i < n; ){  // 固定第一个数
            for(int j = i + 1; j < n; ){  // 固定第二个数
                // 左右双指针
                int left = j + 1, right = n - 1;
                long long rnum = (long long)target - nums[i] - nums[j];
                while(left < right){
                    if(nums[left] + nums[right] > rnum)  right--;
                    else if(nums[left] + nums[right] < rnum)  left++;
                    else{
                        // 尾插
                        ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        // 对 left 和 right 进行去重处理
                        while(left < right && nums[left] == nums[left - 1])  left++;
                        while(left < right && nums[right] == nums[right + 1])  right--;
                    }
                }
                ++j;
                // 对 j 进行去重处理
                while(j < n && nums[j] == nums[j - 1])  j++;
            }
            ++i;
            // 对 i 进行去重处理
            while(i < n && nums[i] == nums[i - 1])  i++;
        }
        return ret;
    }
};

C语言代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 比较函数,用于qsort排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    // 排序
    qsort(nums, numsSize, sizeof(int), compare);

    // 初始化结果数组
    *returnSize = 0;
    int capacity = 100;  // 初始容量,可根据需要调整
    int** ret = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
    for (int i = 0; i < numsSize; ) {
        for (int j = i + 1; j < numsSize; ) {
            int left = j + 1, right = numsSize - 1;
            long long rnum = (long long)target - nums[i] - nums[j];
            while (left < right) {
                long long sum = (long long)nums[left] + nums[right];
                if (sum > rnum) {
                    right--;
                } else if (sum < rnum) {
                    left++;
                } else {
                    // 动态分配内存存储结果
                    if (*returnSize >= capacity) {
                        capacity *= 2;
                        ret = (int**)realloc(ret, capacity * sizeof(int*));
                        *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
                    }
                    ret[*returnSize] = (int*)malloc(4 * sizeof(int));
                    ret[*returnSize][0] = nums[i];
                    ret[*returnSize][1] = nums[j];
                    ret[*returnSize][2] = nums[left];
                    ret[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    // 去重
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重固定第二个数
            j++;
            while (j < numsSize && nums[j] == nums[j - 1]) j++;
        }
        // 去重固定第一个数
        i++;
        while (i < numsSize && nums[i] == nums[i - 1]) i++;
    }
    // 重新分配内存以匹配实际结果数量
    ret = (int**)realloc(ret, *returnSize * sizeof(int*));
    *returnColumnSizes = (int*)realloc(*returnColumnSizes, *returnSize * sizeof(int));
    return ret;
}

Python代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # 对数组进行排序
        n = len(nums)
        ret = []  # 用于存储结果的列表
        for i in range(n):  # 固定第一个数
            # 去重处理:如果当前数字与前一个数字相同,跳过
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n):  # 固定第二个数
                # 去重处理:如果当前数字与前一个数字相同,跳过
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1  # 左右双指针
                rnum = target - nums[i] - nums[j]  # 剩余的目标值
                while left < right:
                    total = nums[left] + nums[right]
                    if total > rnum:
                        right -= 1
                    elif total < rnum:
                        left += 1
                    else:
                        # 找到一个满足条件的四元组
                        ret.append([nums[i], nums[j], nums[left], nums[right]])
                        # 去重处理
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
        return ret
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
1 条评论
热度
最新
可以,大佬,互粉一下
可以,大佬,互粉一下
回复回复点赞举报
推荐阅读
编辑精选文章
换一批
[译] 延迟加载 React Components (用 react.lazy 和 suspense)
虽然在 React 16.8.1 中终于面世的 hooks 引人瞩目,但在去年发布的 16.6.0 版本里也包含了一个吸引人的新特性,可以让我们在不依赖第三方库的情况下简化对延迟加载(lazy loading)的处理。
江米小枣
2020/06/15
3.3K0
搭建React开发环境
1.npx create-react-app my-app 需要node版本>14.x
用户7741497
2022/03/21
3770
【React入门】实现todolist功能
作为一名 PHP 初级的程序员,目前尚且处于学习 PHP 业务逻辑实现到日常工作中的阶段,但是由于现在想要搭建一个满意的个人博客,并且尝试过很多 hexo 主题后总是会对主题的某些或某个部分不太满意, 所以为了以后可以自己实现相应页面的开发,所以还是想着能够学点前端框架的知识,为以后成为全栈工程师做准备。目前比较流行的前端框架主要有React.js和Vue.js,因为当前公司使用的是React.js开发的,所以也选择React作为学习对象。
程序小工
2018/09/12
1.5K0
手把手教你全家桶之React(一)
前言 最近项目用到react,其实前年我就开始接触react,时光匆匆,一直没有时间整理下来(太懒啦)!如今再次用到,称工作间隙,对全家桶做一次总结,项目源码地址。废话不多说,上码。 创建一个文件目录
用户2145235
2018/05/18
9890
Hello React
  至此,Mac环境下react基于脚手架的开发环境已搭建完成。运行项目( npm start)后,浏览器会自动打开本地页面http://localhost:3000/。如果到此步弹出带有react的Logo的欢迎页面,则表示环境已经成功配置。
流眸
2019/08/09
8170
脚手架创建第一个react项目
今天我们使用脚手架来创建属于自己的第一个react项目,来看看创建出来的项目结构是什么样的?在react中又是怎么样的语法~
玖柒的小窝
2021/11/03
3950
react核心api
react从16年12月开始,已经学了有2年多了。react引导了作者找到了第一份比较专职的前端工作。react 2014年横空出世,以其革命性的写法,带动了前端行业的产业升级,尽管比较“重”,却也是笔者至今最喜欢的前端框架,没有之一。
一粒小麦
2019/07/18
7230
React入门系列(一)构建项目
React是一个专注于View层解决方案的框架。于Angular,Vue不同,React并不是完整的MVC/MVVM框架,也不是单纯的模板引擎,它的核心思想就是“组件化”,将UI层拆分为一个个组件,然后组合嵌套,最后构建成完成的APP。
娜姐
2021/01/14
8020
手写一个react,看透react运行机制
react的源码,的确是比vue的难度要深一些,本文也是针对初中级,本意让博友们了解整个react的执行过程。
goClient1992
2022/09/26
2.1K0
「React TS3 专题」从创建第一个 React TypeScript3 项目开始
笔者将介绍两种方式进行构建 React TS3 ( TypeScript3 简称,后面的内容都会以简称出现),分别为使用 create-react-app 进行快速构建 和 手工方式构建。
前端达人
2019/08/28
2.4K0
「React TS3 专题」从创建第一个 React TypeScript3 项目开始
React + Redux 开启 HMR/Hot Loader
最近在用 React 以及 Redux 写几个项目, 使用的是官方 Create-React-App 的脚手架, 默认没有开启 HMR, 每次都要等他自动刷新浏览器效率非常低, 因此考虑使用 HMR 模式
szhshp
2022/09/21
5180
React教程
简介: React 是一个用于构建用户界面的 JAVASCRIPT 库。 React 主要用于构建 UI,很多人认为 React 是 MVC 中的 V(视图)。 React 起源于 Facebook 的内部项目,用来架设 Instagram 的网站,并于 2013 年 5 月开源。 React 拥有较高的性能,代码逻辑非常简单,越来越多的人已开始关注和使用它。
Baige
2022/03/22
7470
React教程
React入门学习笔记
这里的constructor()初始化了props,state.value=null;当点击后,state.value=X;
Mirror王宇阳
2020/12/16
2.7K0
React目录结构详细解析
每个项目的根目录下面,一般都有一个package.json文件,定义了这个项目所需要的各种模块,以及项目的配置信息(比如名称、版本、许可证等元数据)。npm install命令根据这个配置文件,自动下载所需的模块,也就是配置项目所需的运行和开发环境。
先知先觉
2021/12/06
2.5K0
React目录结构详细解析
(1)React的开发
React 使创建交互式 UI 变得轻而易举。为你应用的每一个状态设计简洁的视图,当数据改变时 React 能有效地更新并正确地渲染组件。
达达前端
2019/07/09
7520
React+Flask打造前后端分离项目开发环境
OK,预览下效果,顺便调试(没啥可调试的/(ㄒoㄒ)/~~)。npm start。效果如下:
Cloud-Cloudys
2020/07/06
6.9K2
React 安装
实例中我们引入了三个库: react.development.min.js 、react-dom.development.min.js 和 babel.min.js:
陈不成i
2021/07/29
6180
使用 React 实现页面过渡动画仅需四个步骤【译】
在本文中,我将向你展示如何使用 ReactTransitionGroup 和 Animated 库中的生命周期方法来实现页面的过渡效果。
疯狂的技术宅
2019/03/28
1.4K0
使用 React 实现页面过渡动画仅需四个步骤【译】
React.js基础知识总结一
React是FaceBook(脸书)公司研发的一款JS框架(MVC) React是一款框架:具备自己开发的独立思想(MVC:Model View Controller) -> 划分组件开发 -> 基于路由的SPA单页面开发 -> 基于ES6来编写代码(最后部署上线的时候,我们需要把ES6编译成ES5 =>基于Babel来完成编译) -> 可能用到Less/Sass等,我们也需要使用对应的插件把他们进行预编译 -> 最后为了优化性能(减少HTTP请求次数),我们需要把JS或者CSS进行合并压缩 -> webpack来完成以上页面组件合并、JS/CSS编译加合并等工作
用户6379025
2022/12/26
2.1K0
React.js基础知识总结一
2021年从零开发前端项目指南
之前翻译过一篇 前端工程化发展历史 的文章,Webpack、Babel 、Eslint 现在基本上就是前端项目的标配了。
windliang
2022/09/23
3K0
2021年从零开发前端项目指南
相关推荐
[译] 延迟加载 React Components (用 react.lazy 和 suspense)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验