TLE with both o(n2) methods need help!


  • 0
    Y

    here's my regular O(n2) method:

    class Solution:
        # @return a list of lists of length 3, [[val1,val2,val3]]
        def threeSum(self, num):
            if len(num) < 3:
                return []
            num.sort()
            result = []
            for k in range(1, len(num) - 1):
                i = 0
                j = len(num) - 1
                while i < k and j > k:
                    if num[i] + num[j] == -num[k]:
                        if not [num[i],num[k],num[j]] in result:
                            result.append([num[i],num[k],num[j]])
                        while num[i] == num[i + 1] and i < k:
                            i += 1
                        while num[j] == num[j - 1] and j > k:
                            j -= 1
                        i += 1
                        j -= 1
                    elif num[i] + num[j] < -num[k]:
                        while num[i] == num[i + 1] and i < k:
                            i += 1
                        i += 1
                    else:
                        while num[j] == num[j - 1] and j > k:
                            j -= 1
                        j -= 1
            return result
    

    I have even tried to improve it using binary search

    class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        if len(num) < 3:
            return []
        num.sort()
        result = []
        for k in range(1, len(num) - 1):
            i = 0
            j = len(num) - 1
            self.rec(num,i,k,j,result,True)
    
        return result
    
    def rec(self, num,i,k,j,result, is_left):
        if i >= k or j <= k:
            return
        if is_left:
            tmpRe = self.binary(num, -num[i] - num[k] ,k+1,j)
            if tmpRe == -1:
                while num[i] == num[i + 1] and i < k:
                    i += 1
                i += 1
                self.rec(num, i,k, j,result,True)
            else:
                j = tmpRe
                if not [num[i],num[k],num[j]] in result:
                    result.append([num[i],num[k],num[j]])
                while num[j] == num[j - 1] and j > k:
                    j -= 1
                self.rec(num, i + 1,k, j - 1,result,False)
        else:
            tmpRe = self.binary(num, -num[j] - num[k] ,i,k )
            if tmpRe == -1:
                
                while num[j] == num[j + 1] and j > k:
                    j -= 1
                j -= 1
                self.rec(num, i,k, j,result, False)
            else:
                i = tmpRe
                if not [num[i],num[k],num[j]] in result:
                    result.append([num[i],num[k],num[j]])
                while num[i] == num[i + 1] and i < k:
                    i += 1
                self.rec(num, i + 1,k, j,result,True)
    
    def binary(self, a,key,lo,hi):
        
        if hi < lo:
            return -1
        mid = lo + (hi - lo) / 2
        if hi == lo:
            if key == a[lo]:
                return lo
            else:
                return -1
        if key > a[mid]:
            return self.binary(a,key,mid + 1, hi)
        elif key < a[mid]:
            return self.binary(a,key,lo,mid)
        else:
            return mid
    

    using time.clock(), it only took ~7ms with the TLE test case. Any suggestions?


  • 0
    M
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(), num.end());
        int size = num.size();
        vector<vector<int> > result;
        set<vector<int> > rset;
        for (int i = 0; i < size - 2; i++) {
            int l = i + 1, r = size - 1;
            while (l < r) {
                int sum = num[i] + num[l] + num[r];
                if (sum > 0)
                    r--;
                else if (sum < 0)
                    l++;
                else {
                    vector<int> s;
                    s.push_back(num[i]);
                    s.push_back(num[l]);
                    s.push_back(num[r]);
                    rset.insert(s);
                    l++; r--;
                }
            }
        }
        for (auto it = rset.begin(); it != rset.end(); it++)
            result.push_back(*it);
        return result;
    }
    

    Mine, runs at ~15ms on local computer with the TLE case.

    Not quite sure how to improve it to pass the online judge.


Log in to reply
 

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