two sum变形题挑战一下吧皮卡丘

如果数组中有重复的元素，返回所有unique的数字组合。例如[1, 2, 2, 3, 3, 4, 4, 5], target = 6, 返回：[[1, 5], [2, 4], [3, 3]].

这道题用hash map有同学可解吗？是在想不到办法了，大概有思路但是写不出😭
小弟只能献上大米了！求答案

就是原题hash答案的set 改map吧，map value里存这数是不是在答案里出现过。

这样写？

1. 
   
2. /******************************************************************************
   
3. 
   
4.                               Online C++ Compiler.
   
5.                Code, Compile, Run and Debug C++ program online.
   
6. Write your code in this editor and press "Run" button to compile and execute it.
   
7. 
   
8. *******************************************************************************/
   
9. 
   
10. #include <iostream>
    
11. #include <vector>
    
12. #include <map>
    
13. using namespace std;
    
14. vector<vector<int>> twoSum(vector<int> nums, int target)
    
15. {
    
16.     map<int,int> m;
    
17.     for(int i : nums) m[i]++;
    
18.     vector<pair<int,int>> data(m.begin(), m.end());
    
19.     vector<vector<int>> res;
    
20.     int i=0; int j=data.size()-1;
    
21.     while(i<=j)
    
22.     {
    
23.         if(data[i].first+data[j].first==target)
    
24.         {
    
25.             if(data[i].first != data[j].first || data[i].second>1) res.push_back({data[i].first, data[j].first});
    
26.             i++;j--;
    
27.         }
    
28.         else if(data[i].first+data[j].first < target) i++;
    
29.         else j--;
    
30.     }
    
31.     return res;
    
32. }
    
33. int main()
    
34. {
    
35.     for(auto& i : twoSum({1,2,2,3,3,4,4,5}, 6)) cout << i[0] << " " << i[1] << endl;
    
36. 
    
37.     return 0;
    
38. }
    

复制代码

1. class Solution:
   
2.     def twoSum(nums, target):
   
3.         l, r = 0, len(nums)-1
   
4.         ans = []
   
5.         while l < r:
   
6.             if nums[l] + nums[r] < target:
   
7.                 l += 1
   
8.             elif nums[l] + nums[r] > target:
   
9.                 r -= 1
   
10.             else:
    
11.                 ans.append([nums[l],nums[r]])
    
12.                 repeat = nums[l]
    
13.                 while nums[l] == repeat:
    
14.                     l += 1
    
15.                 repeat = nums[r]
    
16.                 while nums[r] == repeat:
    
17.                     r -= 1
    
18.         return ans
    
19. 
    
20.     nums = [1, 2, 2, 3, 3, 4, 4, 5]
    
21.     target = 6
    
22.     print(twoSum(nums,target))

复制代码

双指针 然后移动指针的时候调到下一个不一样的数字

yyt913 发表于 2021-7-2 15:04
双指针 然后移动指针的时候调到下一个不一样的数字

就是想找arry sort以外的解法谢谢~

two sum返回的是数的index吧，不是数字本身？

先将每个元素都存入集合。遍历每个unique元素x，看看target-x是不是在集合里。是的话，就是一种pair。
当然，还有很多细节，类似于3+3这种情况，要保证元素3至少出现了两次。

data12345 发表于 2021-07-02 00:07:36
就是想找arry sort以外的解法谢谢~

哦哦 我还有个idea就是你每次找到一个组合就把他变成小数在前大数在后的string…然后再用set dedup…如果不在set里就说明是新的…

用set就能解决为啥用map