What's wrong with my solution ? (Output limit)


  • 0
    N

    This is my solution:

    class Solution {
    public:
    
        int search(vector<int> & num, int target, int l, int r) {
            while (l <= r) {
                int m = (l + r) / 2;
                if (num[m] == target) return m;
                else if (num[m] < target) l = m + 1;
                else r = m - 1;
            }
            return -1;
        }
    
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > ans;
            sort(num.begin(), num.end());
            int lastI, lastJ, lastK;
            lastI = lastJ = lastK = 123456789;  // to judge the duplicate triplets
            for (int i = 0; i < num.size(); i++) {
                for (int j = i + 1; j < num.size(); j++) {
                    int pos = search(num, 0 - num[i] - num[j], j + 1, num.size() - 1);  // search the third data
                    if (pos != -1) {
                        if (num[i] == lastI && num[j] == lastJ && num[pos] == lastK) continue;
                        vector<int> a;
                        a.push_back(num[i]);
                        a.push_back(num[j]);
                        a.push_back(num[pos]);
                        ans.push_back(a);
                        lastI = num[i];
                        lastJ = num[j];
                        lastK = num[pos];
                    }
                }
            }
            return ans;
        }
    };

  • 2
    N

    I have found the problem.
    Let's see the case below:
    {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6}
    In this case, when i == 1 and j == 2, we found one solution is {-2, -2, 4};
    But when i == 2 and j == 3, we found a same solution, and the solution can not be delete, because the process to found the 2 solution is not continue.
    To solve this problem, we can make num[i]'s value never repeat.
    Sorry for my poor English.

    class Solution {
    public:
    
        int search(vector<int> & num, int target, int l, int r) {
            while (l <= r) {
                int m = (l + r) / 2;
                if (num[m] == target) return m;
                else if (num[m] < target) l = m + 1;
                else r = m - 1;
            }
            return -1;
        }
    
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > ans;
            sort(num.begin(), num.end());
            int lastI, lastJ, lastK;
            lastI = lastJ = lastK = 123456789;  // to judge the duplicate triplets
            for (int i = 0; i < num.size(); i++) {
                if (i >= 1 && num[i] == num[i - 1]) continue;
                for (int j = i + 1; j < num.size(); j++) {
                    int pos = search(num, 0 - num[i] - num[j], j + 1, num.size() - 1);  // search the third data
                    if (pos != -1) {
                        if (num[i] == lastI && num[j] == lastJ && num[pos] == lastK) continue;
                        vector<int> a;
                        a.push_back(num[i]);
                        a.push_back(num[j]);
                        a.push_back(num[pos]);
                        ans.push_back(a);
                        lastI = num[i];
                        lastJ = num[j];
                        lastK = num[pos];
                    }
                }
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.