LeetCode 15 —— 三数之和

news/2024/9/23 10:30:29/

阅读目录

    • 1. 题目
    • 2. 解题思路
    • 3. 代码实现

1. 题目

2. 解题思路

首先我们对数组进行从小到大排序,然后遍历数组 [ 0 , n u m s . s i z e ( ) − 3 ] [0,nums.size()-3] [0,nums.size()3] 作为三元组中的 a a a,由于三元组的索引互不相同,所以余下的 b b b c c c 我们则只能从 a a a 后面的元素中取,而且 b b b c c c 的索引也不能相同。

假设 a a a 取的是第 i i i 个元素,那么我们让 b b b 首先指向第 i + 1 i+1 i+1 个元素, c c c 首先指向第 n u m s . s i z e ( ) − 1 nums.size()-1 nums.size()1 个也即最后一个元素。这时候,我们检查 a + b + c a+b+c a+b+c 的和与零的关系。

  • 如果二者正好相等,我们保存这个三元组,同时让 b b b 向右移动一步,或者让 c c c 向左移动一步;
  • 如果和小于零,只能让 b b b 向右移动一步;
  • 如果和大于零,则只能让 c c c 向左移动一步。

同时,结果中不能包含重复的三元组,所以 a , b , c a, b,c abc 更新的时候我们都要确保它们不与上一次的值相同

排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),求和时,最外层遍历 a a a 的时间复杂度为 O ( n ) O(n) O(n),内层遍历 b b b c c c 正好把数组访问一遍,时间复杂度也为 O ( n ) O(n) O(n),所以求和的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。所以,整体算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),空间复杂度为 O ( 1 ) O(1) O(1)

3. 代码实现

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int> > ret; sort(nums.begin(), nums.end());int last = nums[0] - 1; // 上一个a,初始化为不和nums[0]相等即可for (int i = 0; i < nums.size()-2; ++i) {if (nums[i] == last) {continue;}int first = i + 1;int first_last_num = nums[first] - 1; // 上一个b,初始化为不和nums[first]相等即可int second = nums.size() - 1;int second_last_num = nums[second] + 1; // 上一个c,初始化为不和nums[second]相等即可while (first != second) {if (nums[first] == first_last_num) {++first;continue;}if (nums[second] == second_last_num) {--second;continue;}int sum = nums[i] + nums[first] + nums[second];if (sum == 0) {ret.push_back({nums[i], nums[first], nums[second]});first_last_num = nums[first++]; // 更新上一次的bsecond_last_num = nums[second]; // 更新上一次的c} else if (sum < 0) {++first;} else {--second;}}last = nums[i]; // 更新上一次的a}return ret;}
};

http://www.ppmy.cn/news/1450309.html

相关文章

[C++基础学习]----05-函数详解

前言 在学习C的基础阶段&#xff0c;函数是一个非常重要的概念。函数是用来完成特定任务的一段代码&#xff0c;它可以被多次调用&#xff0c;并且可以接受参数和返回值。 正文 01-函数简介 函数的定义&#xff1a; 在C中&#xff0c;函数的定义通常包括函数的返回类…

WPF之可翻转面板

1&#xff0c;创建翻转面板的资源字典&#xff1a;FlippPanel.xaml。 无外观控件同样必须给样式指定类型&#xff08; <ControlTemplate TargetType"ss:FlipPanel">&#xff09;&#xff0c;相关详情参考&#xff1a;WPF之创建无外观控件-CSDN博客&#xff09…

Go怎么实现map并发安全的三种方式

1. 加锁 对整个map加上读写锁sync.RWMutex 优点&#xff1a;解决了问题。 缺点&#xff1a;锁粒度大。 2. 分片加锁 一个操作会导致整个map被锁住&#xff0c;导致性能降低。所以提出了分片思想&#xff0c;将一个map分成几个片&#xff0c;按片加锁。 第三方包实现&#x…

Kafka如何将消息发送到指定分区

背景 面试一个时&#xff0c;面试官问了一个问题&#xff0c;Kafka如何做到顺序消息。我回答只给Kafka的Topic创建一个分区&#xff0c;发送到该Topic的消息在Kafka中就是有序的。 面试官又问&#xff0c;如果Topic有多个分区呢&#xff1f;我回答消息发送者在发送消息的时候…

论文笔记总结

写论文不能只讲概念&#xff0c;一定要结合项目理论实际。》例如某xxx具体的项目例子&#xff0c;不能描述某一个软件的功能。 1.历年真题 2.十段式划分&#xff08;回应子题目&#xff0c;三个子题目&#xff09; 3.论文模板&#xff0c;万能模板 4.具体主题相关 第一个主…

js,JavaScript 对象(2024-05-02)

对象是 JavaScript 的数据类型之一。 对象用于存储键/值&#xff08;名称/值&#xff09;集合。 JavaScript 对象是命名值的集合。 下例创建具有四个键/值属性的 JavaScript 对象&#xff1a; const person {firstName: "Bill",lastName: "Gates",age:…

如何下载钉钉群直播回放:完整步骤解析

在当今快节奏的商业和教育环境中&#xff0c;钉钉群直播已经成为了沟通和学习的重要工具。直播结束后&#xff0c;很多观众都希望回顾内容&#xff0c;但却不知如何开始。如果你错过了实时直播&#xff0c;或者只是想再次观看精彩的演讲和讨论&#xff0c;那么下载钉钉群直播回…

Python反射

1、何为反射 1.1、概念 反射&#xff08;Reflection&#xff09;是计算机科学中的一个术语&#xff0c;指的是一种在运行时动态地获取、操作和修改一个语言的特定对象的能力。在编程中&#xff0c;反射可以让程序在运行时动态地获取类的信息&#xff0c;包括类的属性、方法和…