为什么做网站备案的人态度差,鄂尔多斯seo,乐陵市住房和城乡建设局网站,邯郸做网页分析#xff1a; 三数和问题#xff0c;这里和两数之和不一样#xff0c;返回的是值#xff0c;因此可以对其进行排序#xff0c;使用双指针。 一、一层循环双指针 class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort… 分析 三数和问题这里和两数之和不一样返回的是值因此可以对其进行排序使用双指针。 一、一层循环双指针 class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint ans;for(int i0;inums.size()-2;i){if(nums[i]0) break;if(i0nums[i]nums[i-1]) continue;int rightnums.size()-1;int target-nums[i];for(int lefti1;leftright;left){if(lefti1nums[left]nums[left-1]) continue;while(leftrightnums[left]nums[right]target) --right;if(left!right)if(nums[left]nums[right]target) ans.push_back({nums[i],nums[left],nums[right]});}}return ans;}
};
二、一层循环扫一遍的哈希表 为了避免第一层循环不必要的重复值需要进行排序。 无脑往集合里塞然后使用集合去重。由于是全局的哈希表因此i,j和(j,i)都会被放入会有重复。 这里的基本思路是塞入的时候只需要看数量多少即可比如3339那是否真正存在3 个3呢只有两个3是不行的。 时间复杂度On²klogk3klog3 class Solution {
public:void Insert(setvectorint ans ,int a,int b,int c){vectorint temp{a,b,c};sort(temp.begin(),temp.end());ans.insert(temp);return;}vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());setvectorint ans;unordered_mapint,int hash;for(int i0;inums.size();i){if(hash.find(nums[i])hash.end()){hash[nums[i]]1;}else{hash[nums[i]]1;}}for(int i0;inums.size()-2;i){if(nums[i]0) break;if(i0nums[i]nums[i-1]) continue;for(int ji1;jnums.size()-1;j){if(ji1nums[j]nums[j-1]) continue;int cur-nums[i]-nums[j];if(hash.find(cur)!hash.end()){if(curnums[i]||curnums[j]){if(nums[i]nums[j]){if(hash[nums[i]]2) Insert(ans,nums[i],nums[j],cur);}else{if(curnums[i]){if(hash[nums[i]]1) Insert(ans,nums[i],nums[j],cur);}else{if(hash[nums[j]]1) Insert(ans,nums[i],nums[j],cur);}}}else Insert(ans,nums[i],nums[j],cur);}}}vectorvectorint result;for(auto itans.begin();it!ans.end();it){result.emplace_back(*it);}return result;}
};
三、一层循环问一遍 对比一下力扣hot1001.两数之和-CSDN博客 这里问一遍的开销更大了因为每次问都得重开一个集合。清空集合或销毁集合一共O(K)K是不同元素的个数。两数和只需要一个集合没常数级别的判断所以更快 而扫一遍却只需要一个集合用常数级别判断。思路 第一层循环确定一个数i第二层循环 从之后的数开始 从前往后遍历每次遍历时如果这个数j 和 之前存入集合的数 可以构成一个可行解则将结果保存起来并且这个情况下这个数j和它对应的另外一个数 对于数i而言都不能再出现在结果中不然会存在重复确定两个另外一个必然唯一确定。因此当这个数j被存入结果中时下次我们既要 从 与这个数不同的数 开始考虑避免选定同样的两个数也不需要把这个数j存入集合可以存但无意义之和不会再考虑它。 清空set而不是销毁setSet.clear()速度更快 class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint res;for(int i0;inums.size()-2;i){if(nums[i]0) break;//减少不必要的判断if(i0 nums[i]nums[i-1]){continue;}unordered_setint Set;//每次创建一个Set用完这次销毁。int target-nums[i];for(int ji1;jnums.size();j){int temptarget-nums[j];if(Set.find(temp)!Set.end()){res.push_back({nums[i],nums[j],temp});while(jnums.size()-1nums[j]nums[j1]) j;}else{//else 非必要。此时nums[j]可以被存因为tempnums[j]因此nums[j]在后面永远不会被再次考虑存了也不影响结果Set.insert(nums[j]);}}}return res;}
};
