leetcode - 18. 四数之和

zz/2024/5/21 21:19:51

leetcode - 18. 四数之和

题目大意

给定一个数组,要求在这个数组中找出 4 个数之和为 0 的所有组合

解题思路

用 map 提前计算好任意 3 个数字之和,保存起来,可以将时间复杂度降到 O(n^3)。这一题比较麻烦的一点在于,最后输出解的时候,要求输出不重复的解。数组中同一个数字可能出现多次,同一个数字也可能使用多次,但是最后输出解的时候,不能重复。例如 [-1,1,2, -2] 和 [2, -1, -2, 1]、[-2, 2, -1, 1] 这 3 个解是重复的,即使 -1, -2 可能出现 100 次,每次使用的 -1, -2 的数组下标都是不同的。

这一题是第 15 题的升级版,思路都是完全一致的。这里就需要去重和排序了。map 记录每个数字出现的次数,然后对 map 的 key 数组进行排序,最后在这个排序以后的数组里面扫,找到另外 3 个数字能和自己组成 0 的组合。

第 15 题和第 18 题的解法一致。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int> num,int target);
/*
* 1) 对数组进行排序,
* 2) 遍历数组,使用“3Sum”解决问题。
*/
vector<vector<int>> fourSum(vector<int> &num,int target)
{vector<vector<int>> result;if(num.size() < 4) return result;sort(num.begin(),num.end());for(int i = 0;i < num.size() - 3;i++){//跳过重复if(i > 0 && num[i - 1] == num[i]) continue;vector<int> n(num.begin()+i+1, num.end());vector<vector<int>> ret = threeSum(n,target - num[i]);for(int j = 0;j < ret.size();j++){ret[j].insert(ret[j].begin(),num[i]);result.push_back(ret[j]);}}return result;
}vector<vector<int>> threeSum(vector<int> num,int target)
{vector<vector<int>> result;//对数组进行排序(如果数组已经排序了,就不会浪费任何时间)sort(num.begin(),num.end());int n = num.size();for(int i = 0;i < n - 2;i++){//跳过重复if(i > 0 && num[i - 1] == num[i]) continue;int a = num[i];int low = i - 1;int high = n - 1;while(low < high){int b = num[low];int c = num[high];if(a+b+c == target){//得到解决方案vector<int> v;v.push_back(a);v.push_back(b);v.push_back(c);result.push_back(v);//继续搜索总和为零的所有三元组组合。//跳过重复while(low < n && num[low] == num[low + 1]) low++;while(high > 0 && num[high] == num[high - 1]) high--;low++;high--;}else if(a + b + c > target){//跳过重复while(high > 0 && num[high] == num[high - 1]) high--;high--;}else{//跳过重复while(low < n && num[low] == num[low + 1]) low++;low++;}}}return result;
}void printMatrix(vector<vector<int>> &vv)
{for(int i = 0;i < vv.size();i++){cout<<"[";for(int j = 0;j < vv[i].size();j++){cout<<"."<<vv[i][j];}cout<<"]"<<endl;}
}int main()
{int a[] = {1, 0, -1, 0, -2, 2};vector<int> n(a,a+6);int t = 0;vector<vector<int>>v = fourSum(n,t);printMatrix(v);n.clear();int b[] = {-1, -5, -5, -3, 2, 5, 0, 4 };n.insert(n.begin(),b,b+8);t = -7;v = fourSum(n,t);printMatrix(v);return 0;
}

http://www.ngui.cc/zz/2727425.html

相关文章

leetcode - 26. 删除有序数组中的重复项

leetcode - 26. 删除有序数组中的重复项 题目大意 给定一个有序数组 nums&#xff0c;对数组中的元素进行去重&#xff0c;使得原数组中的每个元素只有一个。最后返回去重以后数组的长度值。 解题思路 这道题和第 27 题很像。这道题和第 283 题&#xff0c;第 27 题基本一致…

leetcode - [30. 串联所有单词的子串]

leetcode - [30. 串联所有单词的子串] 题目大意 给定一个源字符串 s&#xff0c;再给一个字符串数组&#xff0c;要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标&#xff0c;如果存在多个&#xff0c;在结果中都需要输出。 解题思路 这一题看似很难&…

leetcode - [35. 搜索插入位置]

leetcode - [35. 搜索插入位置] 题目大意 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 解题思路 给出一个已经从小到大排序…

c++高级编程学习笔记3

函数指针的类型别名 我们通常不考虑函数在内存中的位置&#xff0c;但每个函数实际上都位于某个特定地址。在 C中&#xff0c;可像使用数据那样使用函数。换言之&#xff0c;可使用函数的地址&#xff0c;就像使用变量那样。函数指针的类型取决于兼容函数的参数类型的返回类型…

Qt例子学习笔记 - Examples/Qt-6.2.0/qt3d/basicshapes-cpp

main.cpp //基本形状显示了 Qt 3D 提供的四种基本形状&#xff1a;圆环、圆柱、立方体和球体。 //该示例还展示了如何将 Qt 3D 场景嵌入到小部件中并与其他小部件连接。#include "scenemodifier.h"#include <QGuiApplication> #include <Qt3DRender/qcame…

Qt例子学习笔记 - Examples/Qt-6.2.0/assistant/simpletextviewer

main.cpp #include "mainwindow.h"#include <QApplication> //QApplication 专门为 QGuiApplication 提供了一些基于 QWidget 的应用程序所需的功能。 // 它处理特定于小部件的初始化、完成。 //对于任何使用 Qt 的 GUI 应用程序&#xff0c;无论应用程序在任…

Qt例子学习笔记 - Examples/Qt-6.2.0/charts/customchart

//自定义图表 //我们首先创建一个简单的线系列和一个图表对象。 QLineSeries *series new QLineSeries();*series<<QPointF(0,6)<<QPointF(9,4)<<QPointF(15,20) << QPointF(25, 12) << QPointF(29, 26);QChart *chart new QChart();chart->…

跨平台编译项目

1.linux:INCLUDEPATH “” 2.linux: { message(linux) } 3.message($$QMAKESPAEC) xzxiaqiu:~/study/csdn/day0/test/build$ ls /opt/Qt/Qt6/6.2.0/gcc_64/mkspecs/ aix-g integrity-x86 macx-clang solaris-cc-64 aix-g-64 linux…

布局Layout

布局Layout 1.Vertical Layout 2.Horizontal Layout 3.Grid Layout 4.Form LayoutsizeHint推荐尺寸 1.QSize sizeHint() 推荐尺寸只能重载修改 2.QSize size() 不包含边框的窗口尺寸QSizePolicy::PolicyFlag 1.GrowFlag 必要时可超过推荐 2.ExpandFlag 尽可能的扩展 3.ShrinkF…

QTreeWidgetQTreeWidget

QTreeWidget 1.常用属性 2.标题设置 3.内容插入 4.内容选择 5.拖动和删除 6.信号事件 7.样式qss QTreeWidget 属性 1.header()->setVisible(true) 2.setSortingEnabled点击标题排序 3.setAnimated 动画展开 4.setVerticalScrollBarPolicy setHorizontalScrollBarPolicy滚动…