深圳专业做网站电话,软件开发流程简介,qq哪家公司开发的,有域名怎么建网站第十三章 三数之和四数之和 三数之和
力扣链接
根据题目要求:
返回的数对应的下标各不相同三个数之和等于0不可包含重复的三元组 – – 即顺序是不做要求的 如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组输出答案顺序不做要求
暴力解法: 排序 3个for循环 去重 — — N^3, … 第十三章 三数之和四数之和 三数之和
力扣链接
根据题目要求:
返回的数对应的下标各不相同三个数之和等于0不可包含重复的三元组 – – 即顺序是不做要求的 如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组输出答案顺序不做要求
暴力解法: 排序 3个for循环 去重 — — N^3, 肯定超时 优化: 排序 双指针 去重 — — N^2 优化的具体思路: 固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针) 去重有两种方法: 1.set去重 2 在循环内部缩小空间 — — 非常值得我们去尝试
set去重
class Solution {
public:vectorvectorint threeSum(vectorint nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vectorvectorint res; // 固定一个数 双指针int n nums.size();for(int i 0; i n; i) // 固定一个数{// 双指针优化int left i1, right n-1;int targt -nums[i];while(left right){int sum nums[left] nums[right];if(sum targt){left;}else if(sum targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left;right--;}}}// 去重setvectorint result(res.begin(), res.end());res.clear();for(auto e : result){res.push_back(e);}return res;}
};上面的运行结果太慢了, 我们尝试一下 缩小空间去重
缩小空间去重
class Solution {
public:vectorvectorint threeSum(vectorint nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vectorvectorint res; // 固定一个数 双指针int n nums.size();for(int i 0; i n;) // 固定一个数{// 双指针优化int left i1, right n-1;int targt -nums[i];while(left right){int sum nums[left] nums[right];if(sum targt){left;}else if(sum targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left;right--;// 去重left 和 rightwhile(left right nums[left] nums[left-1]) left;while(right left nums[right] nums[right1]) right--;}}// 去重ii;while(i n nums[i] nums[i-1]) i;}return res;}
};四数之和
力扣链接
这一题就跟上面的题目相似, 思路也很相似: 排序 固定两个数, 双指针优化 去重. 当然, 我们这里的去重逻辑也是 缩小空间去重
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(), nums.end());vectorvectorint res;int n nums.size();// 选定一个数, 内部用三数之和for(int i 0; i n;){// 选定一个数, 内部使用双指针优化for(int j i1; j n;){int left j1, right n-1;long int tar target - (long int)(nums[i]nums[j]);while(left right){long int cur nums[left] nums[right];if(cur tar) left;else if(cur tar) right--;else{res.push_back({nums[i], nums[j], nums[left], nums[right]});left, right--;// 去重left 和 rightwhile(left right nums[left] nums[left-1]) left;while(right left nums[right] nums[right1]) right--;}}// j的去重j;while(j n nums[j] nums[j-1]) j;}// i的去重i;while(i n nums[i] nums[i-1]) i;}return res;}
};号令风霆迅天声动北陬。 长驱渡河洛直捣向燕幽。 马蹀阏氏血旗袅可汗头。 归来报明主恢复旧神州。 — — [宋] 岳飞 送紫岩张先生北伐
