Fuck LeetCode  >  Two Pointers  >  18. 4Sum  >  Solved in Python, JavaScript, Ruby, Java, C++, Go, C#  >  Repost or Contribute

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

    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
    PreviousNext

    1. The idea of this question is the same as 15. 3Sum, please click the link to view.
    2. The difference is that three numbers becomes four numbers, and processing four numbers only requires one more nested loop.
    3. In addition, the target parameter is added, which needs to be brought in as a condition during calculation.
    4. 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)

    Solution in languages: Python JavaScript Ruby Java C++ Go C#

    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;
    }
}
    Solution in languages: Python JavaScript Ruby Java C++ Go C#

    Other languages

    Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 18. 4Sum.
    PreviousNext