Method three_sum

15. 3Sum/src/main.rs:11–42

find three elements in a sorted array O(n^2) fix the first element and find the remaining two elements in the right subvector

(nums: Vec<i32>)

    /// fix the first element and find the remaining two elements
    /// in the right subvector
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums.clone();
        nums.sort();
        let mut ret: Vec<Vec<i32>> = Vec::new();
        if nums.len() < 3 { return ret }
        for i in 0..nums.len()-2 {
            if nums[i] > 0 { break }
            else if i > 0 && nums[i] == nums[i - 1] { continue }
            else {
                let mut l = i + 1;
                let mut r = nums.len() - 1;
                while l < r {
                    if nums[i] + nums[l] + nums[r] < 0 {
                        l += 1
                    } else if nums[i] + nums[l] + nums[r] > 0 {
                        r -= 1
                    } else {
                        ret.push(vec![nums[i], nums[l], nums[r]]);
                        while l < r && nums[l] == nums[l + 1] {
                            l += 1
                        }
                        l += 1;
                        while l < r && nums[r - 1] == nums[r] {
                            r -= 1
                        }
                        r -= 1;
                    }
                }
            }
        }
        ret
    }
}

#[cfg(test)]