数组（9）：4Sum

2023-10-14 20:48

文章标签 数组 4sum

本文主要是介绍数组（9）：4Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

分析：
先排序，然后左右夹逼，时间复杂度为O(n^3)，空间复杂度O(1)；

代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>>result;if(nums.size() < 4)return result;sort(nums.begin(),nums.end());auto last = nums.end();for(auto a = nums.begin();a < prev(last,3);++a){for(auto b = next(a);b < prev(last,2);++b){auto c = next(b);auto d = prev(last);while(c<d){if(*a+*b+*c+*d<target){++c;}else if(*a+*b+*c+*d>target){--d;}else{result.push_back({*a,*b,*c,*d});++c;--d;}}}}sort(result.begin(),result.end());result.erase(unique(result.begin(),result.end()),result.end());return result;}
};

笔记：

1，c++学习之容器——erase()函数
erase()函数用于在顺序型容器中删除容器的一个元素，有两种函数原型，c.erase(p),c.erase(b,e);第一个删除迭代器p所指向的元素，第二个删除迭代器b,e所标记的范围内的元素，c为容器对象，返回值都是一个迭代器，该迭代器指向被删除元素后面的元素（这个是重点）

2，STL之unique()去重函数
unique()是C++标准库函数里面的函数，其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序
对于长度为n数组a，unique(a,a+n) - a返回的是去重后的数组长度
那它是怎么实现去重的呢？删除？
不是，它并没有将重复的元素删除，而是把重复的元素放到数组的最后面藏起来了

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
using namespace std;  
const int N = 100000;  
int a[N+5];  
int main()  
{  int n;  while (cin>>n)  {  for (int i = 0;i < n;++i)  {  scanf("%d",&a[i]);  }  sort(a,a+n);  n = unique(a,a+n) - a;//关键的一句  for (int i = 0;i < n;++i)  {  printf("%d ",a[i]);  }  puts("");  }  return 0;  
}

while (cin>>n)  {  for (int i = 0;i < n;++i)  {  scanf("%d",&a[i]);  }  sort(a,a+n);  int k = unique(a,a+n) - a;  for (int i = 0;i < n;++i)  {  printf("%d ",a[i]);  }  puts("");  }