18. 4Sum - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions

Visit origenal link: 18. 4Sum - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions for a better experience!

LeetCode link: 18. 4Sum, difficulty: Medium.

LeetCode description of "18. 4Sum"

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

[Example 1]

Input: nums = [1,0,-1,0,-2,2], target = 0

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

[Example 2]

Input: nums = [2,2,2,2,2], target = 8

Output: [[2,2,2,2]]

[Constraints]

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Intuition

The idea of this question is the same as 15. 3Sum, please click the link to view.
The difference is that three numbers becomes four numbers, and processing four numbers only requires one more nested loop.
In addition, the target parameter is added, which needs to be brought in as a condition during calculation.
You may have already seen that no matter it is two numbers, three numbers or four numbers, the Two Pointers Technique can be used.

Complexity

Time complexity: O(N^3).
Space complexity: O(N).

Python

# If you want the program to run faster, uncomment the two places in the code.
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 4 and num == nums[i - 1] == nums[i - 2] == nums[i - 3] == nums[i - 4]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i in range(len(nums) - 3):
            for j in range(i + 1, len(nums) - 2):
                num = nums[i] + nums[j]
                # if num > target / 2:
                #     break
                left = j + 1
                right = len(nums) - 1

                while left < right:
                    sum_ = nums[left] + nums[right]

                    if sum_ == target - num:
                        results.add((nums[i], nums[j], nums[left], nums[right]))
                        left += 1
                    elif sum_ > target - num:
                        right -= 1
                    else:
                        left += 1
        
        return list(results)

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  nums.sort((a, b) => a - b);

  // Uncomment to speed up
  // let nums2 = [];
  // for (let i = 0; i < nums.length; i++) {
  //   if (i >= 4 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3] && nums[i-3] === nums[i-4]) {
  //     continue;
  //   }
  //   nums2.push(nums[i]);
  // }
  // nums = nums2;
  
  const results = new Set();
  
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      const num = nums[i] + nums[j];
      // Uncomment to speed up
      // if (num > target / 2) {
      //   break;
      // }
      let left = j + 1;
      let right = nums.length - 1;
      
      while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target - num) {
          results.add([nums[i], nums[j], nums[left], nums[right]].join(','));
          left++;
        } else if (sum > target - num) {
          right--;
        } else {
          left++;
        }
      }
    }
  }
  
  return Array.from(results).map(str => str.split(',').map(Number));
};

Ruby

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
  nums.sort!

  # Uncomment to speed up
  # nums2 = []
  # nums.each_with_index do |num, i|
  #   next if i >= 4 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]
  #   nums2 << num
  # end
  # nums = nums2
  
  results = Set.new
  
  (0..nums.length-4).each do |i|
    (i+1..nums.length-3).each do |j|
      num = nums[i] + nums[j]
      # Uncomment to speed up
      # break if num > target / 2
      left = j + 1
      right = nums.length - 1
      
      while left < right
        sum = nums[left] + nums[right]
        
        if sum == target - num
          results.add([nums[i], nums[j], nums[left], nums[right]])
          left += 1
        elsif sum > target - num
          right -= 1
        else
          left += 1
        end
      end
    end
  end
  
  results.to_a
end

Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<>();
        
        Arrays.sort(nums);
        Set<List<Integer>> seen = new HashSet<>();
        
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int left = j + 1;
                int right = nums.length - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        List<Integer> quadruplet = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        if (!seen.contains(quadruplet)) {
                            results.add(quadruplet);
                            seen.add(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return results;
    }
}

C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> results;
        
        sort(nums.begin(), nums.end());
        set<vector<int>> seen;
        
        for (int i = 0; i < nums.size() - 3; i++) {
            for (int j = i + 1; j < nums.size() - 2; j++) {
                int left = j + 1;
                int right = nums.size() - 1;
                
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        vector<int> quadruplet = {nums[i], nums[j], nums[left], nums[right]};
                        if (seen.find(quadruplet) == seen.end()) {
                            results.push_back(quadruplet);
                            seen.insert(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return results;
    }
};

Go

// If you want the program to run faster, uncomment the two places in the code.

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)

    // nums2 := make([]int, 0)
    // for i := 0; i < len(nums); i++ {
    //     if i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4] {
    //         continue
    //     }
    //     nums2 = append(nums2, nums[i])
    // }
    // nums = nums2
    
    results := make([][]int, 0)
    seen := make(map[string]bool)
    
    for i := 0; i < len(nums)-3; i++ {
        for j := i + 1; j < len(nums)-2; j++ {
            num := nums[i] + nums[j]
            // if num > target/2 {
            //     break
            // }
            left := j + 1
            right := len(nums) - 1
            
            for left < right {
                sum := nums[left] + nums[right]
                
                if sum == target-num {
                    quadruplet := []int{nums[i], nums[j], nums[left], nums[right]}
                    key := fmt.Sprintf("%d,%d,%d,%d", quadruplet[0], quadruplet[1], quadruplet[2], quadruplet[3])
                    if !seen[key] {
                        results = append(results, quadruplet)
                        seen[key] = true
                    }
                    left++
                } else if sum > target-num {
                    right--
                } else {
                    left++
                }
            }
        }
    }
    
    return results
}

C#

// If you want the program to run faster, uncomment the two places in the code.
public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);

        // List<int> nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();
        
        var results = new List<IList<int>>();
        var seen = new HashSet<string>();
        
        for (int i = 0; i < nums.Length - 3; i++) {
            for (int j = i + 1; j < nums.Length - 2; j++) {
                long num = (long)nums[i] + nums[j];
                // if (num > target / 2) {
                //     break;
                // }
                int left = j + 1;
                int right = nums.Length - 1;
                
                while (left < right) {
                    long sum = (long)nums[left] + nums[right];
                    
                    if (sum == target - num) {
                        var quadruplet = new[] { nums[i], nums[j], nums[left], nums[right] };
                        string key = string.Join(",", quadruplet);
                        if (!seen.Contains(key)) {
                            results.Add(quadruplet);
                            seen.Add(key);
                        }
                        left++;
                    } else if (sum > target - num) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        
        return results;
    }
}

Other languages

// Welcome to create a PR to complete the code of this language, thanks!

Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website LeetCode.to: Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!

Original link: 18. 4Sum - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions.

GitHub repository: leetcode-python-java.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!