当前位置: 首页 > news >正文

15.三数之和(双指针,C解答附详细分析)

题目描述:

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

优秀解答:

int cmp(const void* pa, const void* pb){int a=*(int*)pa;int b=*(int*)pb;return a>b?1:-1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int base=100;//数组的初始长度,可更改//初始化处理返回值,二维数组的大小和保存每一个一维数组大小的数组的空间保持一致int** res=(int**)malloc(sizeof(int*)*base);*returnColumnSizes=(int*)malloc(sizeof(int)*base);*returnSize=0;int i,j,k;//排序qsort(nums,numsSize,sizeof(int),cmp);for(i=0;i<numsSize;i++){//先确定第三个数的值,再对剩下的两个数进行两数之和的操作//若本次的第三个数与上一次的情况相同,则跳过这个数if(i>0&&nums[i]==nums[i-1])continue;//给定nums[i],以j,k作为双指针进行两数之和操作j=i+1;k=numsSize-1;while(j<k){int sum=nums[i]+nums[j]+nums[k];if(sum==0){//刚好遇见符合要求的三元组//申请返回值二维数组的空间res[*returnSize]=(int*)malloc(sizeof(int)*3);//每一个数组大小都为3(*returnColumnSizes)[*returnSize]=3;//给申请的空间赋值res[*returnSize][0]=nums[i];res[*returnSize][1]=nums[j];res[*returnSize][2]=nums[k];//二维数组的行数加1(*returnSize)++;//如果二维数组的大小达到初始设定的行数,则进行空间扩容if(*returnSize==base){base*=2;res=(int**)realloc(res,sizeof(int*)*base);*returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*base);}//记录符合要求的两个数,进行去重int num1=nums[j],num2=nums[k];while(nums[j]==num1&&j<k)j++;while(nums[k]==num2&&j<k)k--;}//若三个数之和小于0,则左边的指针右移else if(sum<0)j++;//若三个数的之和大于0,则右边的指针往左移else k--;}}return res;
}

解答来自用户:烟火

分析:本题用C语言实在复杂,涉及到二维数组的空间分配,有很多细节需要注意。

1.区分指针,指针的值,指向指针的指针。

        本题中res是一个二维数组,为指向int指针的指针,可以理解为一个元素为int指针的一维数组。由于题解写在函数里,函数内部定义的变量都属局部变量,而return只能返回一个参数,所以用指针returnSize返回三元组的个数。

        用指向指针的指针returnColumnSizes返回每一行数组的长度。(非常绕,多想一想!)原作者给出的解释为“而在三数之和中,要求我们返回的其实是一个二维数组,那么我们除了需要知道二维数组的行数,每一行的数组的长度也是需要返回的,这就是另一个参数int** returnColSize 的用途,至于为什么这里也是一个指向指针的指针,因为returnColSize是我们从外部传进来的一个指针参数,要想保证在函数中对该指针的改变对外部产生影响,那么我们在外部传入的时候,也应该按照传引用的方式传入一个指针的地址,反映到函数中就是一个指向指针的指针。”

        returnSize作为一个int类型的指针,*returnSize为指针指向的值,即一个int值,可以用res[*returnSize]索引二维数组的行。还需要注意增加三元组个数时(*returnSize)++;的括号,如果不加括号则成了使指针值递增,而不是使指针指向的int元素递增。

        总结一下,res是一个指向指针的指针,指向存储答案的二维数组,其中每一个符合要求的三元组为一行;returnColumnSizes是一个指针,指向存储了每行大小(本题固定为3)的一维数组;returnSize是一个指针,指向三元组的个数,即二维数组的行数。

2.C语言中未知大小数组的空间分配。

        C语言中的数组分配必须要有固定大小,给解题增加了难度。本题作者定义了一个初始大小base进行空间分配,在每次循环中都要比较当前三元组个数是否超过了分配的大小,如果空间不够用增加base大小,调用realloc(res,sizeof(int*)*base);在原来的基础上增加分配空间。以此实现变长数组。malloc分配空间,realloc增加空间,calloc分配初始化为0的空间。

3.解题思路分析。

        先通过排序使数组有序,再依次遍历数组元素 i ,对于每个 i ,定义 j 初始指向剩余元素中的最小元素,定义 k 初始指向剩余元素中的最大元素,若三者和小于0,则将 j 右移,使得新的三数和更大,更有机会满足要求,否则 k 右移。这是双指针移动的一种基本思路,与题目11.盛水最多的容器相同, j 和 k 都不走回头路,使得二者移动的步数加起来为n,而若用暴力解的双层for循环则为n平方。故本题的解题思路可以理解为进行了n次11题的循环。

相关题目链接:11.盛水最多的容器(双指针,C解法)-CSDN博客

相关文章:

15.三数之和(双指针,C解答附详细分析)

题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含…...

SpringCloud微服务 【实用篇】| Dockerfile自定义镜像、DockerCompose

目录 一&#xff1a;Dockerfile自定义镜像 1. 镜像结构 2. Dockerfile语法 3. 构建Java项目 二&#xff1a; Docker-Compose 1. 初识DockerCompose 2. 部署微服务集群 前些天突然发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;…...

Vue3+TS+ElementPlus的安装和使用教程【详细讲解】

前言 本文简单的介绍一下vue3框架的搭建和有关vue3技术栈的使用。通过本文学习我们可以自己独立搭建一个简单项目和vue3的实战。 随着前端的日月更新&#xff0c;技术的不断迭代提高&#xff0c;如今新vue项目首选用vue3 typescript vite pinia……模式。以前我们通常使用…...

浅析锂电池保护板(BMS)系统设计思路(四)SOC算法-扩展Kalman滤波算法

BMS开发板 1 SOC估算方法介绍 电池SOC的估算是电池管理系统的核心&#xff0c;自从动力电池出现以来&#xff0c;各种各样的电池SOC估算方法不断出现。随着电池管理系统的逐渐升级&#xff0c;电池SOC估算方法的效率与精度不断提高&#xff0c;下面将介绍常用几种电池SOC估算方…...

构建异步高并发服务器:Netty与Spring Boot的完美结合

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 ChatGPT体验地址 文章目录 前言IONetty1. 引入依赖2. 服务端4. 客户端结果 总结引导类-Bootstarp和ServerBootstrap连接-NioSocketChannel事件组-EventLoopGroup和NioEventLoopGroup 送书…...

uniapp实现文字超出宽度自动滚动(在宽度范围之内不滚动、是否自动滚动、点击滚动暂停)

效果如下: 文字滚动 组件代码: <template><view class="tip" id="tip" @tap.stop="clickMove"><view class=...

win11 电脑睡眠功能失效了如何修复 win11 禁止鼠标唤醒

1、win11睡眠不管用怎么办&#xff0c;win11电脑睡眠功能失效了如何修复 在win11系统中拥有许多令人激动的新功能和改进&#xff0c;有些用户在使用win11电脑时可能会遇到一个问题&#xff1a;睡眠模式不起作用。当他们尝试将计算机置于睡眠状态时&#xff0c;却发现系统无法进…...

内坐标转换计算

前言 化学这边的库太多了。 cs这边的库太少了。 去看化学的库太累了。 写一个简单的实现思路&#xff0c;让cs的人能看懂。 向量夹角的范围 [0, pi) 这是合理的。 因为两个向量只能构成一个平面系统&#xff0c;平面系统内的夹角不能超过pi。 二面角的范围 涉及二面角&…...

vue中 components自动注册,不需要一个个引入注册方法

1.在compontents文件夹新建js文件 componentRegister 不能引用文件夹里的组件** import Vue from "vue"; function capitalizeFirstLetter(string) { return string.charAt(0).toUpperCase() string.slice(1); } const requireComponent require.context( ".…...

web自动化测试从入门到持续集成

在很多刚学习自动化的可能会认为我只需要会运用selenium&#xff0c;我只需要在一个编辑器中实用selenium java编写了一些脚本那么就会自动化了&#xff0c;是真的吗&#xff1f;答案肯定是假的。自动化肯定是需要做到真的完全自动化&#xff0c;那如何实现呢&#xff1f;接着往…...

python小工具之弱密码检测工具

一、引用的python模块 Crypto&#xff1a; Python中一个强大的加密模块&#xff0c;提供了许多常见的加密算法和工具。它建立在pyc.ypodome或pyc.ypto等底层加密库之上&#xff0c;为Python程序员提供了简单易用的API&#xff0c;使其可以轻松地实现各种加密功能。 commands…...

链接器--动态链接器--延迟绑定与动态链接器是什么?学习笔记二

内容在下面链接&#xff08;通过新建标签页打开&#xff09;&#xff1a; 链接器--动态链接器--延迟绑定与动态链接器是什么&#xff1f;学习笔记二一个例子来看延迟加载https://mp.weixin.qq.com/s?__bizMzkyNzYzMjMzNA&mid2247483713&idx1&snee90a5a7d59872287…...

JMeter CSV 参数文件的使用方法

.在 JMeter 测试中&#xff0c;参数化是非常重要的&#xff0c;参数化允许我们模拟真实世界中的各种情况。本文我们将探讨如何在 JMeter 中使用 CSV 参数文件。 创建 CSV 文件 首先&#xff0c;我们需要创建一个逗号分隔的值&#xff08;CSV&#xff09;文件&#xff0c;其中…...

how2heap-2.23-06-unsorted_bin_into_stack

#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h>// 从 unsorted bin 的 bk 去找合适的 void jackpot(){ fprintf(stderr, "Nice jump d00d\n"); exit(0); }int main() {intptr_t stack_buffer[4] {0};fpr…...

(学习打卡2)重学Java设计模式之六大设计原则

前言&#xff1a;听说有本很牛的关于Java设计模式的书——重学Java设计模式&#xff0c;然后买了(*^▽^*) 开始跟着小傅哥学Java设计模式吧&#xff0c;本文主要记录笔者的学习笔记和心得。 打卡&#xff01;打卡&#xff01; 六大设计原则 &#xff08;引读&#xff1a;这里…...

数据结构:第7章:查找(复习)

目录 顺序查找&#xff1a; 折半查找&#xff1a; 二叉排序树&#xff1a; 4. (程序题) 平衡二叉树&#xff1a; 顺序查找&#xff1a; ASL 折半查找&#xff1a; 这里 j 表示 二叉查找树的第 j 层 二叉排序树&#xff1a; 二叉排序树&#xff08;Binary Search Tree&…...

编程语言的未来?

编程语言的未来&#xff1f; 随着科技的飞速发展&#xff0c;编程语言在计算机领域中扮演着至关重要的角色。它们是软件开发的核心&#xff0c;为程序员提供了与机器沟通的桥梁。那么&#xff0c;在技术不断进步的未来&#xff0c;编程语言的走向又将如何呢&#xff1f; 在技…...

SpringBoot的测试

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

C++睡眠函数:Windows平台下的Sleep函数和Linux平台的usleep函数

C/C睡眠函数&#xff1a;Windows平台下的Sleep函数和Linux平台的usleep函数 WinAPI Sleep Sleep函数属于Windows API&#xff0c;使用它需要先包含synchapi.h。 void Sleep(DWORD dwMilliseconds);函数仅有一个参数&#xff08;睡眠时长&#xff09;&#xff0c;单位是毫秒。…...

详解白帽子以及红队、蓝队和紫队

企业继续数字化&#xff0c;其关键基础设施和运营扩大了攻击面&#xff0c;暴露于各种威胁途径的面前。为了解决这个问题&#xff0c;企业领导者认识到拥有内部专家的重要性。考虑到网络威胁领域不断发展的态势&#xff0c;企业领导者可以利用道德黑客以及红队、蓝队和紫队的工…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...