C# solution using a dictionary


  • 1
    B

    The basis of this solution is that we keep track of the counts of certain sums in our dictionary for the first two lists (or just of the lists in general). We then iterate through the other two, negating the sums. We know that if we find the negated value of the sums in the dictionary, then we have a complete sum that equals 0. For example, the dictionary contains -2. As we're iterating through the second two lists, we see that sum of the values equals 2. We know that that would be a valid tuple since -2 + 2 = 0. We just need to check to make sure the -2 exists.

    public class Solution {
        public int FourSumCount(int[] A, int[] B, int[] C, int[] D) {
            IDictionary<int, int> dict = new Dictionary<int, int>();
            int result = 0;
            
            for(int i = 0; i < A.Length; i++) {
                for(int j = 0; j < B.Length; j++) {
                    int value = A[i] + B[j];
                    
                    if(dict.ContainsKey(A[i] + B[j])) {
                        dict[value]++;
                    }
                    else {
                        dict[value] = 1;
                    }
                }
            }
            
            for(int i = 0; i < C.Length; i++) {
                for(int j = 0; j < D.Length; j++) {
                    int negatedValue = -1 * (C[i] + D[j]);
                    
                    if(dict.ContainsKey(negatedValue)) {
                        result += dict[negatedValue];
                    }
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

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