C# Hashmap and 2-Pointer Solution


  • 0
    L

    2-pointer Solution - 500ms

    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        //1,1,1,2,2,2,3,3,3,4,4,4,5,6,7,8   15
        for(int i = 0; i < nums.Length - 3; i++){
            if(i - 1 >= 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < nums.Length - 2; j++){
                if(j - 1 > i && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.Length - 1;
                while(left < right)
                    if(nums[left] + nums[right] == target - nums[i] - nums[j]){
                        result.Add(new List<int>(new int[]{nums[i], nums[j], nums[left++], nums[right--]}));
                        while(left < nums.Length && nums[left] == nums[left - 1]) left++;
                        while(right > j && nums[right] == nums[right + 1]) right--;
                    }
                    else if(nums[left] + nums[right] < target - nums[i] - nums[j]) left++;
                    else right--;
            }
        }
        return result;
    }
    
    public IList<IList<int>> FourSum(int[] nums, int target){
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 3; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.Length - 2; j++){
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int sum = target - nums[i] - nums[j], left = j + 1, right = nums.Length - 1;
                while (left < right){
                    if (nums[left] + nums[right] == sum){
                        List<int> lst = new List<int>();
                        lst.Add(nums[i]); lst.Add(nums[j]);
                        lst.Add(nums[left]); lst.Add(nums[right]);
                        result.Add(lst);
                        left++; right--;
                        while (left < nums.Length && nums[left] == nums[left - 1]) left++;
                        while (right > j + 1 && nums[right] == nums[right + 1]) right--;
                    }
                    else if (nums[left] + nums[right] < sum) left++;
                    else if (nums[left] + nums[right] > sum) right--;
                }
            }
        }
        return result;
    }
    

    Hashmap (Dictionary) Solution -- 800ms

    public static IList<IList<int>> FourSum(int[] nums, int target){
        Array.Sort(nums);
        Dictionary<int, int> dict = new Dictionary<int, int>();
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 3; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.Length - 2; j++){
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int sum = target - nums[i] - nums[j];
                for (int k = j + 1; k < nums.Length; k++)
                    if (dict.ContainsKey(nums[k])){
                        List<int> lst = new List<int>();
                        lst.Add(nums[i]); lst.Add(nums[j]);
                        lst.Add(nums[dict[nums[k]]]); lst.Add(nums[k]);
                        result.Add(lst);
                        while (k < nums.Length - 1 && nums[k + 1] == nums[k]) k++;
                    }
                    else dict[sum - nums[k]] = k;
                dict.Clear();
            }
        }
        return result;
    }

Log in to reply
 

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