今天復(fù)習(xí)自己寫了下3sum ,仿照2sum伙单，我自然想到用hash-map
但是在這里情況有所不同：
- array 里面可能有重復(fù)數(shù)字 eg.
[-1,0,1,2,-1,-4] - 可能漏解，以及出現(xiàn)重復(fù)解 eg. 我的解決方案有[2,-4,2]，因為在查找第三個數(shù)字的時候map里面的確存在，但是只出現(xiàn)一次密末。 漏掉了[-1,-1,2]這一情況，原因是在建立map 時候出現(xiàn)了 muti key->one value.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
vector<int> sol(3,0);
map<int,int> hash_map;
for (int i = 0; i < nums.size(); i++)
{
int sum = -nums[i];
for (int j = i+1; j < nums.size(); j++)
{
if(hash_map.find(sum-nums[j])!=hash_map.end()){
sol[0]=nums[i];
sol[1]=nums[j];
sol[2]=-nums[i]-nums[j];
result.push_back(sol);
}
}
hash_map[i]=nums[i];
}
return result;
}
改為搜索的方法
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // for fix number only use once
int left = i + 1;
int right = nums.size() - 1; // use two curcor from left ,right to middle
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
result.push_back({nums[i], nums[left], nums[right]});
left++;
right--;
}
else if (nums[i] + nums[left] + nums[right] > 0)
right--;
else if (nums[i] + nums[left] + nums[right] < 0)
left++;
}
}
return result;
}
還有些問題
√ Your Input: [-2,0,0,2,2]
√ Output (8 ms): [[-2,0,2],[-2,0,2]]
√ Expected (0 ms): [[-2,0,2]]
沒有處理重復(fù)解，可見要一次寫出完全正確的解還是很難的楞捂。
