[leetcode 454] 4Sum II

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

 

문제 풀이:

map을 사용한다. 배열이 4개가 아니라 2개라고 가정해보자

A B만 있다고 가정할 때 합이 0이 되기 위해선 A를 기준으로 -1과 -2가 필요할 것이다. B에 -1과 -2가 모두 있으므로 결과값은 2가 될 것이다.

 

배열 4개로 돌아와보자.

A+B 배열과 C+D배열 두 개로 나눈다. 

 

C+D 배열의 경우의 수를 미리 맵에 저장해놓는다. 배열로 하고 싶지만 범위가 2^28인데다가 음수까지 있어서 offset처리하면 배열 범위를 벗어난다.

그래서 맵을 정의해서 각 합의 등장횟수를 카운트한다.

그 다음 A+B를 한 모든 경우의 수에 -를 곱한 수를 맵에서 찾는다.

class Solution {
public:
    
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int len = A.size();
        
        if(len == 0){
            return 0;
        }
        
        if(len == 1){
            return (A[0] + B[0] + C[0] + D[0] == 0? 1: 0);
        }
        
        unordered_map<int, int> um;
        
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                um[C[i] + D[j]]++;
            }
        }
        
        int result = 0;
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                int tmp = A[i] + B[j];
                if(um.count(-tmp)>0){

                    result += um[-tmp];
                }
            }
        }
                                
        return result;
    }
};