How to use Binary Search with "4Sum II"?


  • 1
    S

    This question has "Binary Search" as a tag but in the solutions proposed (in discuss) I don't see it used. How is that?
    Is it actually possible to use binary search to solve such problem?


  • 0
    L

    @SergeGardien Yes~first add x (foreach in vector A) and y (foreach in vector B) ,put the sum into vector s,do the same to vector C,D and new vector called m; for every x in new vector s, we find how many -x in vector m, use binary search to do this ,This is the binary search code:

        int biSearch(vector<int> & nums,int x,bool LEFT) {
            int l = 0, r = nums.size()-1, m = 0;
            while (l <= r) {
                m = (l+r)>>1;
                if (LEFT) {
                    if (nums[m] >= x) r = m - 1;
                    else l = m + 1;
                }
                else {
                    if (nums[m] <= x) l = m + 1;
                    else r = m - 1;
                }
            }
            return LEFT?l:r;
        }
    

    we only need to call biSearch(m,-s[i],false)-biSearch(m,-s[i],true)+1 to calc the number of -s[i] in vector m;
    This is my code, 216ms beats 89.09%

    class Solution {
    public:
        int biSearch(vector<int> & nums,int x,bool LEFT) {
            int l = 0, r = nums.size()-1, m = 0;
            while (l <= r) {
                m = (l+r)>>1;
                if (LEFT) {
                    if (nums[m] >= x) r = m - 1;
                    else l = m + 1;
                }
                else {
                    if (nums[m] <= x) l = m + 1;
                    else r = m - 1;
                }
            }
            return LEFT?l:r;
        }
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
            vector<int> s;
            vector<int> m;
            int sum = 0, ans = 0, n = A.size();
            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < n; ++ j) {
                    s.push_back(A[i]+B[j]);
                    m.push_back(C[i]+D[j]);
                }
            }
            sort(s.begin(),s.end());
            sort(m.begin(),m.end());
            for (size_t i = 0; i < s.size(); ++ i) {
                if (i != 0 && s[i] == s[i-1]) ans += sum;
                else {
                    sum = biSearch(m,-s[i],false)-biSearch(m,-s[i],true)+1;
                    ans += sum;
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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