LeetCode 15. 3Sum

3Sum.

My solution here is to use a hash table to achieve a O(n2) performance. Basically you can just brute force two number, and check if the last number exists for checking the hash table. There is a less space intensive solution (but harder to understand.) I use it in the 3Sum Closest problem.

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        IList<IList<int>>  ret = new List<IList<int>>();
        if (nums.Length == 0) return ret;
        foreach(int i in nums){
            if(dict.ContainsKey(i)) dict[i] += 1;
            else dict[i] = 1;
        }
        Array.Sort(nums);
        for(int i = 0; i < nums.Length && nums[i] <= 0; i++){ if(i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.Length && nums[j] + nums[i] <= 0; j++){ if(j > i+1 && nums[j] == nums[j-1]) continue;
                int k = 0 - nums[j] - nums[i];
                if (k < nums[j]) continue; int count = 1; if (k == nums[j]) count += 1; if (k == nums[i]) count += 1; if (dict.ContainsKey(k) && dict[k] >= count){
                    IList<int> tuple = new List<int>();
                    tuple.Add(nums[i]);
                    tuple.Add(nums[j]);
                    tuple.Add(k);
                    ret.Add(tuple);
                }
            }
        }
        return ret;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *