Leetcode第十八题(四数之和)

简介: 这篇博客介绍了LeetCode第18题“四数之和”的解法,通过排序和双指针技术来找出数组中所有和为特定值的四个不同元素的组合。

题目描述:

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1:输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

​
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        //寻找第三个,第四个数
        for(int i = 0; i < nums.size(); i++){
            //去重
            if(i > 0 && 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;
                //寻找第一个跟第二个数
                int sum = target - nums[i] - nums[j];
                int l = j + 1,r = nums.size() - 1;
                while(l < r){
                    if(sum == nums[l] + nums[r]){
                        ans.push_back({nums[i],nums[j],nums[l],nums[r]});
                        while(l < r && nums[l] == nums[l + 1]) l++;
                        while(l < r && nums[r] == nums[r - 1]) r--;
                        l++,r--;
                    }
                    else if(sum < nums[l] + nums[r])
                        r--;
                    else
                        l++;
                }
            }
        }
        return ans;
    }
};

​
AI 代码解读

在十五题三数之和的基础之上, 在外层套一层循环寻找第四个数

目录
打赏
0
0
0
0
25
分享
相关文章
mac下完全卸载Node.js
mac下完全卸载Node.js
1030 0
SpringBoot2.x系列教程31--SpringBoot整合H2内存数据库实现CRUD操作
前言 在上一章节中,我给大家详细讲解了H2数据库的安装配置,接下来我就带大家在Spring Boot中整合H2数据库,实现代码操作。 一. 以内嵌模式整合H2数据库 1. 创建Web项目 我们按照之前的经验,创建一个SpringBoot的Web程序,具体过程略,请参考下图创建。 2. 添加依赖包 然后在pom.xml文件中添加如下依赖包。 <dependency> <groupId>com.h2database</groupId> <artifactId>h2</artifactId> <scope>runtime</scope> </dependency> <de
1764 1
SpringBoot2.x系列教程31--SpringBoot整合H2内存数据库实现CRUD操作
|
9月前
|
Leetcode第二十二题(括号生成)
这篇文章讨论了如何使用递归算法解决LeetCode第22题“括号生成”的问题,提供了两种C++的实现方法,目的是生成所有有效的括号组合。
75 0
Leetcode第二十二题(括号生成)
|
9月前
|
🏗️Java零基础:深入了解Java 堆
【10月更文挑战第2天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
92 3
【技术贴】if-else VS switch:谁才是Java条件判断的王者?
【6月更文挑战第14天】本文探讨了Java中if-else与switch语句的选择问题。if-else基于布尔逻辑,适合处理复杂逻辑,而switch在处理多分支特别是枚举类型时更高效。if-else在条件动态变化或复杂逻辑时更合适,switch则因其跳转表机制在固定选项中表现优秀。性能上,switch在大量选项时占优,但现代JVM优化后两者差异不大。选择时应考虑场景、可读性和维护性,灵活运用。理解两者特点,才能写出优雅高效的代码。
635 0
LLM主流开源代表模型(二)
随着ChatGPT迅速火爆,引发了大模型的时代变革,国内外各大公司也快速跟进生成式AI市场,近百款大模型发布及应用。
邮箱API发送邮件调试的方法和步骤
AokSend指南:调试邮箱API发送邮件涉及确认调试目的、检查参数设置、接口调用、异常处理、日志记录及结果验证。确保参数正确,关注接口返回,记录日志以分析问题,处理异常情况,最终验证邮件发送成功与内容准确性。AokSend提供高效发信服务,支持SMTP/API接口,适用于大量验证码发送。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问