漯河网站超市建设,软件开发的五个阶段,宿迁市宿城区二手房最新消息,山东省建设执业注册中心网站这道题在使用哈希表来做时#xff0c;做的很吃力#xff0c;对重复的去除很费劲。
首先是对i的去重#xff0c;不能使用nums[i] nums[i] 这样的条件去判断#xff0c;这会遗漏掉类似[-1, -1 , 2]这样的解其次是对j的去重#xff0c; 对j的去重是为了防止类似[-4, 2, 2, …这道题在使用哈希表来做时做的很吃力对重复的去除很费劲。
首先是对i的去重不能使用nums[i] nums[i] 这样的条件去判断这会遗漏掉类似[-1, -1 , 2]这样的解其次是对j的去重 对j的去重是为了防止类似[-4, 2, 2, 2], [0, 0, 0, 0]这类数组的重复的解的出现如果使用nums[j] nums[j 1] nums[j1] nums[j2], 此时for循环需要改为 j nums.size() - 2但这样就会漏掉数组的最后两个元素。哈希表set每个 i 需要重新创建否则之前存在set中的值会影响判断造成重复的解三数之和的求解是对数组进行遍历然后将问题分解为 n 个两数之和去求解。 代码如下
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint threeSum;int i,j,k;sort(nums.begin(), nums.end());for(i 0; i nums.size(); i){if(nums[i] 0){return threeSum;}if(i 0 nums[i] nums[i - 1]){continue;}unordered_setint s;for(j i 1; j nums.size(); j){if(j i 2 nums[j] nums[j - 1] nums[j - 1] nums[j - 2]){continue;}k 0 - nums[i] - nums[j];if(s.find(k) ! s.end()){threeSum.push_back( {nums[i], nums[j], k} );s.erase(k);} else {s.insert(nums[j]);}}}return threeSum;}
};第二种写法是只用双指针的写法对排序后的升序数组left指向i1right指向nums.size() - 1。
当三个数相加小于0时left当三个数相加大于0时right–当三个数相加等于0时则对left和right进行去重然后同时左右收缩
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint threeSum;sort(nums.begin(), nums.end());for(int i 0; i nums.size(); i){if(nums[i] 0){return threeSum;}if(i 0 nums[i] nums[i - 1]){continue;}int left i 1;int right nums.size() - 1;while(left right){if(nums[i] nums[left] nums[right] 0){threeSum.push_back({nums[i], nums[left], nums[right]});while(right left nums[right] nums[right - 1]){right--;}right--;while(right left nums[left] nums[left 1]){left;}left;}else if(nums[i] nums[left] nums[right] 0){left;}else {right--;}}}return threeSum;}
};
