leetcode 15 三数之和
LeetCode 15 三数
2023-09-27 14:29:24 时间
三数之和
map法
数组变成map,key是数组值,value是数组下标,
之后双层循环,在map的key里面找到0-nums(j)-nums(j),再检查下标是否相同
最后对key排序,在结果里没出现就加入
#include <iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include <algorithm>
#include<map>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
unordered_map<int, int> num_map;
vector<int> sum_1;
vector<vector<int>> sum;
for (int i = 0; i < nums.size(); i++)
{
num_map.insert(pair<int, int>(nums[i], i));
}
for (int i = 0; i < nums.size(); i++)
{
for (int j = i+1; j < nums.size(); j++)
{
auto iter = num_map.find(0 - nums[i] - nums[j]);
if (iter != num_map.end() )
{
if ((*iter).second != i && (*iter).second != j )
{
sum_1.push_back(nums[i]);
sum_1.push_back(nums[j]);
sum_1.push_back((*iter).first);
sort(sum_1.begin(), sum_1.end());
if (find(sum.begin(), sum.end(), sum_1) == sum.end())
{
sum.push_back(sum_1);
}
sum_1 = {};
}
}
}
}
return sum;
}
};
int main() {
Solution a;
vector<int> nums = { -1,0,1,2,-1,-4 };
vector<vector<int>> sum;
sum = a.threeSum( nums);
for (int i = 0; i < sum.size(); i++)
{
for (int j = 0; j < sum[0].size(); j++)
cout << sum[i][j] << " ";
cout << endl;
}
return 0;
}
双指针法
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 错误去重a方法,将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
*/
// 正确去重a方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组
/*
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
*/
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时,双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
二刷
哈希法(最后超时)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
unordered_map<int,int> my_map;
sort(nums.begin(),nums.end());
for(int i=0 ; i<nums.size()-1;i++)
{
for(int j=i+1 ; j<nums.size();j++)
{
auto it= my_map.find(0 - nums[i] - nums[j]);
if( it != my_map.end() )
{
vector<int> tmp = { nums[it->second] , nums[i] , nums[j]};
if(find(result.begin(),result.end(),tmp) == result.end())
result.push_back(tmp);
tmp.clear();
}
}
my_map.insert(pair<int,int>(nums[i],i));
}
return result;
}
};
双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
int left ,right;
for(int i=0 ; i<nums.size()-1;i++)
{
if(nums[i] > 0) break;
if(i>0 && nums[i] == nums[i-1]) continue;
left = i+1;
right = nums.size()-1;
while(left<right)
{
if(nums[i] + nums[left] + nums[right] > 0)
right--;
else if(nums[i] + nums[left] + nums[right] < 0)
left++;
else if(nums[i] + nums[left] + nums[right] == 0)
{
vector<int> tmp={nums[i] , nums[left] , nums[right]};
result.push_back(tmp);
while(left<right && nums[right]==nums[right-1]) right--;
while(left<right && nums[left]==nums[left+ 1]) left++;
right--;
left++;
}
}
}
return result;
}
};
高频题
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
int j,k;
for(int i=0 ; i<nums.size() ;i++)
{
if(nums[i] > 0) break;
if(i>0 && nums[i] == nums[i-1]) continue;
j = i+1;
k = nums.size()-1;
while(j<k)
{
if (nums[i] + nums[j] + nums[k] >0) k--;
else if(nums[i] + nums[j] + nums[k] <0) j++;
else if(nums[i] + nums[j] + nums[k] == 0)
{
result.push_back({nums[i],nums[j],nums[k]});
while(j<k && nums[k] == nums[k-1]) k--;
while(j<k && nums[j] == nums[j+1]) j++;
k--;
j++;
}
}
}
return result;
}
};
相关文章
- 【LeetCode】数据流的中位数 [H](堆)
- LeetCode_二叉树_中等_剑指 Offer 26.树的子结构
- LeetCode_多指针_二分搜索_中等_792.匹配子序列的单词数
- LeetCode_动态规划_中等_368.最大整除子集
- LeetCode_回溯_动态规划_中等_131.分割回文串
- LeetCode_二叉树_简单_100.相同的树
- LeetCode_回溯_困难_51.N 皇后
- LeetCode_双指针_中等_16.最接近的三数之和
- LeetCode·每日一题·1700.无法吃午餐的学生数量·模拟
- LeetCode·每日一题·850.矩形面积 || ·【离散化+扫描线+数组】
- [LeetCode] 752. Open the Lock 开锁
- [LeetCode] 804. Unique Morse Code Words 独特的摩斯码单词
- leetcode 179 最大数
- leetcode 53 最大子数组和