получение дубликатов в 3sum с помощью хеширования - PullRequest
Новая
       20

получение дубликатов в 3sum с помощью хеширования

1 голос
/ 09 мая 2019

Я занимался проблемой трех сумм 3SUM Я знаю, что лучшим решением будет использование двух указателей.Но я попробовал с хешированием, я смог решить проблему, но я получил дубликаты триплетов.Хотя я пытался удалить дубликаты, но все же получал их. 

// C++ program to find a triplet using Hashing 
#include <iostream>
#include<unordered_set>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> output;
        unordered_set<int> seen;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            //removing duplicates
            if (i != 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.size(); ++j) {
                if (seen.count(-nums[i] - nums[j])) {
                    output.push_back({ nums[i], nums[j], -nums[i] - nums[j] });
                    // Skip duplicates
                    while (j + 1 < nums.size() && nums[j + 1] == nums[j]) ++j;
                }
                seen.insert(nums[j]);
            }
        }
        return output;
    }
};



/* Driver program to test above function */
int main()
{
    vector<int> A = { -1,0,1,2,-1,-4 };
    int sum = 13;
    int arr_size = sizeof(A) / sizeof(A[0]);
    vector<vector<int>> v;

    Solution s;
    v=s.threeSum(A);
    //printing duplicates here
    for (auto p : v) {
        for (auto m : p) {
            cout << m<<" ";
        }
        cout << endl;
    }

    return 0;
}
...