FourSumII [source code]


public class FourSumII {
static
/******************************************************************************/
public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int n = A.length;
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map.computeIfAbsent(A[i] + B[j], key -> new ArrayList<int[]>()).add(new int[]{i,j});
        int count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                int sum = C[i] + D[j];
                List<int[]> ls = map.get(0 - sum);
                if (ls != null)
                    count += ls.size();
            }
        return count;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FourSumII.Solution tester = new FourSumII.Solution();
    }
}

先想笨办法..想了一下没什么思路, 那么reduce到我们熟悉的问题呢? 比如4sum问题? 好像是可以做的. 好的, 我们想到了4sum, 但是要知道, 4sum其实也是两种做法来做的; 这里我们用那种? 普通的4->3->2的思路, 还是4=2+2的思路? 如果是第一种, 那么复杂度肯定是N^3了, 但是我瞄了一下discussion, 好像最优解是N^2. 那么感觉是用第二种方法的可能性多一点了; 尝试一下看能不能写出来;

另外这个题目好像不需要像4sum那么麻烦的处理duplicate问题了? 因为我们最后要找的是index, 而编程的iteration的最直接的iteration就是based on index, rather than value, 所以只要你保证index不重复, 最后就不会有重复, 这个则相对来说是很好保证的;

想了一下, 第二种方法好像其实也是还是N^3, 如果WorstCase的话? 这个在之前4sum的时候看那个答案的时候那个人已经解释清楚了; //不对, 实际上自己动手写了代码之后就发现了, 这里这个duplicate的情形简化了之后, 实际代码比4sum要简单, 我们第二个循环每一个iteration最后需要得到的只是一个长度, 而不是把这个list整个都走一遍, 所以最后还真的是可以得到N^2的速度;

最后的速度是263ms (14%), 还是有点失望的, 感觉应该是有什么优化没有想到.

这个是discussion的最优解:

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {  
    Map<Integer, Integer> map = new HashMap<>();  

    for(int i=0; i<C.length; i++) {  
        for(int j=0; j<D.length; j++) {  
            int sum = C[i] + D[j];  
            map.put(sum, map.getOrDefault(sum, 0) + 1);  
        }  
    }  

    int res=0;  
    for(int i=0; i<A.length; i++) {  
        for(int j=0; j<B.length; j++) {  
            res += map.getOrDefault(-1 * (A[i]+B[j]), 0);  
        }  
    }  

    return res;  
}

提速技巧: 避免overkill, down-power your solution;

当我在第二个循环发现只需要size的时候, 我并没有意识到这个想法可以进一步简化第一个循环本身; 因为最后要返回的是count, 所以历史信息里面记录的只要是count就行了, 而不是我那样把整个所有的index pair都记录下来;

另外我写的时候还没有注意, 事实上这个算法是不需要sort的; 就是用类似2sum的Map做法那样, 最直接的历史信息流思路来做就行了;

另外, 即使是这个算法, 也有一个更加naive的写法:

Using 2 hash maps for each of possible sums in both (A,B) and (C,D) find number of occurrences of this sum. Then, for each sum in (A,B) we can find if (C,D) contains complimentary sum. Add (this sum occurrences(a,b)) * (complimentary sum occurrences(c,d)) to the result.

这种维护两个历史信息流的做法当然是可以的, 但是也是因为overkill, 所以不如这里这种只维护第一个历史信息流, 然后check the second on the fly的做法快;

当然这种算法背后的思路你可以理解为先把算法问题数学化, 然后再来处理数学信息, 这种思路有时候确实会让问题简单一些;

class Solution {  
public:  
    void fillMap(vector<int>& A, vector<int>& B, unordered_map<int,int> &m)  
    {  
        int n = A.size();  
        for(int i = 0; i < n; ++i)  
        for(int j = 0; j < n; ++j)  
          ++m[A[i] + B[j]];  

    }  
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {  
        unordered_map<int,int> m1, m2;  
        fillMap(A, B, m1);  
        fillMap(C, D, m2);  
        int res = 0;  
        for(auto it = m1.begin(); it != m1.end(); ++it)  
        {  
           auto it2 = m2.find(-it->first);  
           if(it2 != m2.end())  
             res += it->second * it2->second;  
        }  
        return res;  
    }  
};

注意最后的这个乘法;

一个人提供的thinking process:

The naive solution is to run four loops by iterating all elements and check for (A[i] + B[j] + C[k] + d[h]) == 0. Time complexity: N^4
We can improve solution by iterating through elements of three arrays and check if the fourth array contains A[i] + B[j] + C[k] + d == 0 ----> d = -A[i] - B[j] - C[k]. We can use HashSet to store elements of fourth array. Overall time complexity: N^3;
To improve the solution we can divide arrays into two parts. Then make calculation of sums of one part (A[i] + B[j]) and store their sum's occurences counter in a HashMap. While calculating second part arrays' sum (secondSum = C[k] + D[h]) we can check whether map contains secondSum*(-1);

除开这些, 这个问题的discussion好像也就这样了;

Problem Description

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:  
A = [ 1, 2]  
B = [-2,-1]  
C = [-1, 2]  
D = [ 0, 2]  

Output:  
2  

Explanation:  
The two tuples are:  
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0  
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Difficulty:Medium
Total Accepted:17.8K
Total Submissions:38.2K
Contributor: Samuri
Related Topics
binary search hash table
Similar Questions
4Sum

LC454 FourSumII

FourSumII [source code]

提速技巧: 避免overkill, down-power your solution;

Problem Description

results matching ""

No results matching ""