3sum

Array Two Pointers Sorting

38.6% acceptance

Jan 12, 2026

35232

3263

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    let mut result: Vec<Vec<i32>> = Vec::new();
    
    // Sort the array to use two-pointer technique
    nums.sort_unstable();
    
    let n = nums.len();
    
    // Iterate through the array
    for i in 0..n {
      // Skip duplicate elements for the first number
      if i > 0 && nums[i] == nums[i - 1] {
        continue;
      }
      
      // If the smallest number is positive, no triplet can sum to 0
      if nums[i] > 0 {
        break;
      }
      
      // Two-pointer approach for the remaining array
      let mut left = i + 1;
      let mut right = n - 1;
      
      while left < right {
        let sum = nums[i] + nums[left] + nums[right];
        
        if sum == 0 {
          result.push(vec![nums[i], nums[left], nums[right]]);
          
          // Skip duplicates for the second number
          while left < right && nums[left] == nums[left + 1] {
            left += 1;
          }
          
          // Skip duplicates for the third number
          while left < right && nums[right] == nums[right - 1] {
            right -= 1;
          }
          
          left += 1;
          right -= 1;
        } else if sum < 0 {
          left += 1;
        } else {
          right -= 1;
        }
      }
    }
    
    result
  }
}