赞
踩
哈希篇,继续。
记录 十九【15. 三数之和】
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 //这两行虽然i,j,k不一样,但是3个元素是:-1,-1,0,如果都输出,认为[-1,-1,0]重复
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
(陷入哈希法使用,方法单一)
(1)从提示:数组长度不算小,每个元素最大为105,求和之后,值也不小。从两数之和那道题思路,第一步,确定使用哈希法。(这是一种思路陷井,没有反应出来别的方法(参考所学的双指针法))
(2)刚刚完成“四数相加”的题目,所以考虑求a+b作为key,对应元素对作为value,使用map结构。然后遍历nums,找到c的相反数。
(3)先把整个nums重复的元素去掉,但是重复元素可以求和,所以得记录重复次数。所以用一个map结构(还没有说顺序),key是nums元素,value是元素出现次数。key不能重复,所以排除multimap。那么用unordered_map还是map?继续(4)分析。
(4)怎么在一个map中找到 三个元素和为0?肯定得遍历。
得找it = nums_nondup.find(0- i->first - j->first);
如果it == nums.end(),肯定下一轮;
当it != nums.end(),找到元素(还要去重):
1.如果it指向的元素 > j指向的元素,肯定没重复,因为没遍历到那里。可以push到返回值中;
2.在it指向的元素 <= j指向的元素下:
A.如果(it指向的元素 = j指向的元素)&& (i指向的nums != j指向的nums):得看j元素有没有多出现?至少出现2次,才能nums[j] = nums[k];可以push到返回值中;
B.如果(it指向的元素 = j指向的元素)&& (i指向的nums == j指向的nums):如示例3,得看元素是不是至少出现3次。才能nums[i]=nums[j] = nums[k];可以push到返回值中;
C.剩下情况:不可以push因为已经遍历过。
所以如何不重复是一个难点。判断可不可以push到返回值中,也有情况讨论。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; map<int,int> nums_nondup;//元素值作为key,出现次数作为value,按顺序 map<int,int>::iterator j; //去重,记录出现的次数。 for(int x: nums){ nums_nondup[x]++; } //开始遍历,i指针是最外层循环 for(auto i = nums_nondup.begin();i != nums_nondup.end();++i){ if(i->second > 1){ //出现多次 j = i; }else{ j = next(i,1); } //第二层,nums[j] for(j;j != nums_nondup.end();++j){ auto it = nums_nondup.find(0- i->first - j->first); //找nums[k] if(it != nums_nondup.end()){ //能不能push_back,也要分情况判断 if((it->first > j->first)){ result.push_back({i->first,j->first,it->first}); }else if(it == j && j != i && it->second >= 2){ result.push_back({i->first,j->first,it->first}); }else if(j == i && it == j && it->second >= 3){ result.push_back({i->first,j->first,it->first}); } } } } return result; } };
(1)因为“四数相加”的题目,是把nums1和nums2的和作为key,对应下标对;在思路(3)没有nums去重之前的思路,在去重之后,还想尝试。可是仍然有重复。
解释:以示例一nums = [-1,0,1,2,-1,-4],
思路(3)之后得到nums_nondup内的元素:<-4,1>、<-1,2>、<0,1>、<1,1>、<2,1>。
用另一个unordered_map<int,vector<vector<int>>> sum;中key是不重复元素之和,value对应元素对。(每个key对应的元素对不可能重复,因为nums_nondup去重过)
在sum结构中:
和为0:对应元素对有[-1,1];
和为1:对应元素对有[0,1];
当在nums_nondup遍历nums[k]第三个元素时:遍历到0,找到和为0,0加入到[-1,1]中。遍历到-1,找到和为1,-1加入到[0,1]。如果push到返回数组中,仍然得到重复三元组。(因为输出顺序不重要,[-1,1,0]和[0,1,-1]认为是一样的。)
总结:这一步不成功,所以回归到思路(4)直接遍历。
回归题目,传的参数一个数组nums,三个元素来源于同一个数组。也就是在一个数组中找、进行操作;数组操作方法在数组篇学到双指针法。
双指针法:组成一个区间,逐步移动区间大小或者位置。
双指针思路:
代码实现:
//根据新思路再次实现 class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> result; for(int i = 0;i < nums.size();i++){ if(i > 0&& nums[i] == nums[i-1]){ continue; } int j = i+1; int 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{ result.push_back({nums[i],nums[j],nums[k]}); //放的是元素值 j++; //先移动,再去重。 k--; while(j < k && nums[k] == nums[k+1]){ k--; } while(j < k && nums[j] == nums[j-1]){ j++; } } } } return result; } };
实现区别:
else部分,是先移动还是先去重?
如果是先移动,k和后一个元素比;j和前一个元素比。(个人实现)
如果是先去重,k和前一个元素比,直到前一个和当前不一样,指向重复元素的第一个;j和后一个元素比,直到后一个和当前不一样,指向重复元素的最后一个。再同时k--;j++。(参考)
(1)思路应该打开,只要是学过的方法,都可以尝试。可能相近题目“两数之和”、“四数之和”、“三叔之和”背后不是一种方法。
(欢迎指正,转载表明出处)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。