4sum

Array Two Pointers Sorting

40.1% acceptance

Jan 12, 2026

12780

1533

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut nums = nums;
    nums.sort_unstable();
    let n = nums.len();
    let mut result = Vec::new();
    
    if n < 4 {
      return result;
    }
    
    for i in 0..n-3 {
      // Skip duplicates for first number
      if i > 0 && nums[i] == nums[i-1] {
        continue;
      }
      
      for j in i+1..n-2 {
        // Skip duplicates for second number
        if j > i+1 && nums[j] == nums[j-1] {
          continue;
        }
        
        let mut left = j + 1;
        let mut right = n - 1;
        
        while left < right {
          // Use i64 to avoid overflow
          let sum = nums[i] as i64 + nums[j] as i64 + nums[left] as i64 + nums[right] as i64;
          let target_i64 = target as i64;
          
          if sum == target_i64 {
            result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
            
            // Skip duplicates for third number
            while left < right && nums[left] == nums[left + 1] {
              left += 1;
            }
            // Skip duplicates for fourth number
            while left < right && nums[right] == nums[right - 1] {
              right -= 1;
            }
            
            left += 1;
            right -= 1;
          } else if sum < target_i64 {
            left += 1;
          } else {
            right -= 1;
          }
        }
      }
    }
    
    result
  }
}