4Sum LeetCode solution in Rust

1
use std::cmp::Ordering;
2

3
impl Solution {
4
  pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
5
    let mut combinations: Vec<Vec<i32>> = vec![];
6
    let len = nums.len();
7

8
    if len < 4 {
9
      return combinations;
10
    } // can't have multiple of 4
11

12
    // Convert the Vec<i32> to Vec<i64> to handle large numbers.
13
    let mut nums: Vec<i64> = nums.into_iter().map(|x| x as i64).collect();
14
    let target = target as i64;
15

16
    nums.sort_unstable(); // sort to allow left/right crawling
17

18
    for i in 0..len - 3 {
19
      if nums[i] * 4 > target {
20
        break; // no more solutions can be found if left most index (i) cannot divide/4 evenly or less than target
21
      } // considering all numbers right of (i) are either equal or larger!
22

23
      // traverse duplicates
24
      if i > 0 && nums[i] == nums[i - 1] {
25
        continue;
26
      }
27

28
      for j in i + 1..len - 2 {
29
        if nums[j] * 3 > target - nums[i] {
30
          continue; // continue j loop if second left most index (j) cannot divide/3 evenly or less than target - i
31
        }
32

33
        // traverse duplicates
34
        if j > i + 1 && nums[j] == nums[j - 1] {
35
          continue;
36
        }
37

38
        let (mut left, mut right) = (j + 1, len - 1);
39

40
        while left < right {
41
          let cur_val = nums[i] + nums[j] + nums[left] + nums[right];
42
          match cur_val.cmp(&target) {
43
            Ordering::Equal => {
44
              // if equal, push solution
45
              combinations.push(vec![
46
                nums[i] as i32,
47
                nums[j] as i32,
48
                nums[left] as i32,
49
                nums[right] as i32,
50
              ]);
51

52
              // pull left and right inwards
53
              left += 1;
54
              right -= 1;
55

56
              // then traverse any duplicates
57
              while left < right && nums[left] == nums[left - 1] {
58
                left += 1;
59
              }
60
              while left < right && nums[right] == nums[right + 1] {
61
                right -= 1;
62
              }
63
            }
64
            Ordering::Less => left += 1, // if sum is less move left to find a larger sum
65
            Ordering::Greater => right -= 1, // if sum is greater move right to find a smaller sum
66
          }
67
        }
68
      }
69
    }
70
    combinations
71
  }
72
}