Leetcode 18. 4Sum

4Sum.

This problem is similar to the previous 3SumĀ problem, just add one more layer of fixed numbers. The complexity will be O(n3).

Different to the 3Sum problem though, this one required to return the solution set, which doesn’t allow duplicate solutions. You may need to remove the duplication carefully.

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        IList<IList<int>> res = new List<IList<int>>();
        if(nums.Length < 4) return res;
        Array.Sort(nums);
        for(int i = 0; i < nums.Length - 3; i++){
            while(i != 0 && nums[i] == nums[i-1]) i++;
            for(int j = i+1; j < nums.Length - 2; j++){
                while(j != i+1 && j < nums.Length - 2 && nums[j] == nums[j-1]) j++;
                if(j >= nums.Length - 2) break;
                int left = j+1;
                int right = nums.Length - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        List<int> sol = new List<int>();
                        sol.Add(nums[i]);
                        sol.Add(nums[j]);
                        sol.Add(nums[left]);
                        sol.Add(nums[right]);
                        res.Add(sol);
                        right -= 1;
                        left += 1;
                        while(right > left && nums[right] == nums[right+1]) right -= 1;
                        while(right > left && nums[left] == nums[left-1]) left += 1;
                    } else if (sum > target){
                        right -= 1;
                        while(right > left && nums[right] == nums[right+1]) right -= 1;
                    } else {
                        left += 1;
                        while(right > left && nums[left] == nums[left-1]) left += 1;
                    }
                    
                }
            }
        }
        return res;
    }
}

Leave a Reply

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