🚀 Level Up Your Developer Identity

While mastering algorithms is key, showcasing your talent is what gets you hired.

We recommend leader.me — the ultimate all-in-one personal branding platform for programmers.

The All-In-One Career Powerhouse:

• 📄 Resume, Portfolio & Blog: Integrate your skills, GitHub projects, and writing into one stunning site.
• 🌐 Free Custom Domain: Bind your own personal domain for free—forever.
• ✨ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

Build Your Programmer Brand at leader.me →

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

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.

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

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

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

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

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

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.

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

# 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)

/**
 * @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));
};

# @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

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;
    }
}

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;
    }
};

// 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
}

// 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;
    }
}

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

🚀 Level Up Your Developer Identity

While mastering algorithms is key, showcasing your talent is what gets you hired.

We recommend leader.me — the ultimate all-in-one personal branding platform for programmers.

The All-In-One Career Powerhouse:

• 📄 Resume, Portfolio & Blog: Integrate your skills, GitHub projects, and writing into one stunning site.
• 🌐 Free Custom Domain: Bind your own personal domain for free—forever.
• ✨ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

Build Your Programmer Brand at leader.me →

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

GitHub repository: leetcode-python-java.