0015.三数之和.md

解题关键点

• 先对输入的数组进行排序
• 两重循环，内层采用左右双指针进行遍历，可以使时间复杂度降到 O(n^2)
• 主要的坑是，三个指针都必须跳过重复项

代码

impl Solution {
    // 改写了默认的函数声明，把参数改为 mutable 的
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        // 涉及到成员类型泛型，所以没办法让程序自动推断
        let mut res: Vec<Vec<i32>> = Vec::new();
        // 缓存 len，好像不缓存也不会降低运行效率，但是这么写代码看起来简洁一点
        let len = nums.len();
        // 少于 3 项直接返回空
        if len < 3 {
            return res;
        }
        // 指针 i 只需要遍历到 len - 2
        for i in 0..(len - 2) {
            // 跳过重复项
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            // left 指针从 i + 1 开始递增
            let mut left = i + 1;
            // right 指针从结尾开始递减
            let mut right = len - 1;
            while left < right {
                let sum = nums[i] + nums[left] + nums[right];
                if sum == 0 {
                    // 得到题解
                    res.push(vec![nums[i], nums[left], nums[right]]);
                }
                if sum >= 0 {
                    right -= 1;
                    // 跳过重复项
                    while right > 0 && nums[right] == nums[right + 1] {
                        right -= 1;
                    }
                }
                if sum <= 0 {
                    left += 1;
                    // 跳过重复项
                    while left < len - 1 && nums[left] == nums[left - 1] {
                        left += 1;
                    }
                }
            }
        }
        return res;
    }
}

改进了一版，把指针计算逻辑提取出来，不过指针计算还存在重复逻辑，暂时未解决兼容正序循环和逆序循环的问题

// 向量参数要借用
pub fn cacl_index(nums: &Vec<i32>, from: usize, to: usize) -> usize {
    let mut prev = nums[from];
    if from <= to {
        for i in from..to {
            if prev != nums[i] {
                return i;
            }
            prev = nums[i];
        }
    } else {
        // 迭代器的逆序循环使用 .rev() 方法
        for i in (to..from).rev() {
            if prev != nums[i] {
                return i;
            }
            prev = nums[i];
        }
    }
    return to;
}

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res: Vec<Vec<i32>> = Vec::new();
        let len = nums.len();
        if len < 3 {
            return res;
        }
        for i in 0..(len - 2) {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            let mut left = i + 1;
            let mut right = len - 1;
            while left < right {
                let sum = nums[i] + nums[left] + nums[right];
                if sum == 0 {
                    res.push(vec![nums[i], nums[left], nums[right]]);
                }
                if sum >= 0 {
                    // 传递借用的 nums
                    right = cacl_index(&nums, right, left);
                }
                if sum <= 0 {
                    left = cacl_index(&nums, left, right);
                }
            }
        }
        return res;
    }
}

测试用例

    assert_eq!(vec![] as Vec<Vec<i32>>, three_sum(vec![]));
    assert_eq!(vec![] as Vec<Vec<i32>>, three_sum(vec![-1,-1,-1,-1]));
    assert_eq!(vec![] as Vec<Vec<i32>>, three_sum(vec![1,1,1,1]));
    assert_eq!(vec![vec![0,0,0]], three_sum(vec![0,0,0,0,0]));
    assert_eq!(vec![vec![-82,-11,93],vec![-82,13,69],vec![-82,17,65],vec![-82,21,61],vec![-82,26,56],vec![-82,33,49],vec![-82,34,48],vec![-82,36,46],vec![-70,-14,84],vec![-70,-6,76],vec![-70,1,69],vec![-70,13,57],vec![-70,15,55],vec![-70,21,49],vec![-70,34,36],vec![-66,-11,77],vec![-66,-3,69],vec![-66,1,65],vec![-66,10,56],vec![-66,17,49],vec![-49,-6,55],vec![-49,-3,52],vec![-49,1,48],vec![-49,2,47],vec![-49,13,36],vec![-49,15,34],vec![-49,21,28],vec![-43,-14,57],vec![-43,-6,49],vec![-43,-3,46],vec![-43,10,33],vec![-43,12,31],vec![-43,15,28],vec![-43,17,26],vec![-29,-14,43],vec![-29,1,28],vec![-29,12,17],vec![-14,-3,17],vec![-14,1,13],vec![-14,2,12],vec![-11,-6,17],vec![-11,1,10],vec![-3,1,2]], three_sum(vec![34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49]));