[LC 454] 4SumII

This problem can be solved in O(n^2). General solution: for each two arrays, remember the number of pairwise sum using a map, and then go through the maps to find if the keys add to the target value.
Though not used in this solution, it is helpful to note a few points in binary search that returns the number of target values in the given array.
  private int search(int[] a, int v) {
         // this part is the standard binary search 
        int i = 0, j = a.length-1;
        int mid = 0;
        while (i <= j) {
            mid = i + (j-i) / 2;
            if (a[mid] < v) {
                i = mid + 1;
            } else if (a[mid] > v) {
                j = mid – 1;
            } else {
                break;
            }
        }
        
        if (a[mid] != v) return 0;
        int count = 0;
        i = mid;
        while (i < a.length && a[i++] == v) count++; //  check the array boundary before accessing the elements
        i = mid;
        while (i > 0 && a[–i] == v) count++; // –i here, otherwise the a[mid] is counted twice
        return count;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s