15.三数之和(双指针,C解答附详细分析)
题目描述:
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != 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解答附详细分析)
题目描述: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含…...

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

Vue3+TS+ElementPlus的安装和使用教程【详细讲解】
前言 本文简单的介绍一下vue3框架的搭建和有关vue3技术栈的使用。通过本文学习我们可以自己独立搭建一个简单项目和vue3的实战。 随着前端的日月更新,技术的不断迭代提高,如今新vue项目首选用vue3 typescript vite pinia……模式。以前我们通常使用…...

浅析锂电池保护板(BMS)系统设计思路(四)SOC算法-扩展Kalman滤波算法
BMS开发板 1 SOC估算方法介绍 电池SOC的估算是电池管理系统的核心,自从动力电池出现以来,各种各样的电池SOC估算方法不断出现。随着电池管理系统的逐渐升级,电池SOC估算方法的效率与精度不断提高,下面将介绍常用几种电池SOC估算方…...

构建异步高并发服务器:Netty与Spring Boot的完美结合
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 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睡眠不管用怎么办,win11电脑睡眠功能失效了如何修复 在win11系统中拥有许多令人激动的新功能和改进,有些用户在使用win11电脑时可能会遇到一个问题:睡眠模式不起作用。当他们尝试将计算机置于睡眠状态时,却发现系统无法进…...

内坐标转换计算
前言 化学这边的库太多了。 cs这边的库太少了。 去看化学的库太累了。 写一个简单的实现思路,让cs的人能看懂。 向量夹角的范围 [0, pi) 这是合理的。 因为两个向量只能构成一个平面系统,平面系统内的夹角不能超过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,我只需要在一个编辑器中实用selenium java编写了一些脚本那么就会自动化了,是真的吗?答案肯定是假的。自动化肯定是需要做到真的完全自动化,那如何实现呢?接着往…...

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

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

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

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设计模式之六大设计原则
前言:听说有本很牛的关于Java设计模式的书——重学Java设计模式,然后买了(*^▽^*) 开始跟着小傅哥学Java设计模式吧,本文主要记录笔者的学习笔记和心得。 打卡!打卡! 六大设计原则 (引读:这里…...

数据结构:第7章:查找(复习)
目录 顺序查找: 折半查找: 二叉排序树: 4. (程序题) 平衡二叉树: 顺序查找: ASL 折半查找: 这里 j 表示 二叉查找树的第 j 层 二叉排序树: 二叉排序树(Binary Search Tree&…...
编程语言的未来?
编程语言的未来? 随着科技的飞速发展,编程语言在计算机领域中扮演着至关重要的角色。它们是软件开发的核心,为程序员提供了与机器沟通的桥梁。那么,在技术不断进步的未来,编程语言的走向又将如何呢? 在技…...

SpringBoot的测试
🙈作者简介:练习时长两年半的Java up主 🙉个人主页:程序员老茶 🙊 ps:点赞👍是免费的,却可以让写博客的作者开心好久好久😎 📚系列专栏:Java全栈,…...
C++睡眠函数:Windows平台下的Sleep函数和Linux平台的usleep函数
C/C睡眠函数:Windows平台下的Sleep函数和Linux平台的usleep函数 WinAPI Sleep Sleep函数属于Windows API,使用它需要先包含synchapi.h。 void Sleep(DWORD dwMilliseconds);函数仅有一个参数(睡眠时长),单位是毫秒。…...
详解白帽子以及红队、蓝队和紫队
企业继续数字化,其关键基础设施和运营扩大了攻击面,暴露于各种威胁途径的面前。为了解决这个问题,企业领导者认识到拥有内部专家的重要性。考虑到网络威胁领域不断发展的态势,企业领导者可以利用道德黑客以及红队、蓝队和紫队的工…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...