15. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn three_sum(mut v: Vec<i32>) -> Vec<Vec<i32>> {
        v.sort();
        let mut ans = vec![];
        for i in 0..v.len() - 2 {
            if i > 0 && v[i] == v[i - 1] {
                continue;
            }
            let mut j = i + 1;
            let mut k = v.len() - 1;
            while j < k {
                if v[j] + v[k] + v[i] == 0 {
                    ans.push(vec![v[i], v[j], v[k]]);
                    j += 1;
                    while j < k && v[j] == v[j - 1] {
                        j += 1
                    }
                    k -= 1;
                    while j < k && v[k] == v[k + 1] {
                        k -= 1
                    }
                } else if v[j] + v[k] < -v[i] {
                    j += 1
                } else {
                    k -= 1
                }
            }
        }
        ans
    }
}
}

双指针做法还是想不到

学习感想

想不到用双指针

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res: Vec<Vec<i32>> = Vec::new();
        for i in 0..nums.len() - 2usize {
            if i > 0 && nums[i] == nums[i-1usize] { continue }
            let mut left: usize = i + 1usize;
            let mut right: usize = nums.len() - 1usize;
            use std::cmp::Ordering;
            while left < right {
                let s: i32 = nums[i] + nums[left] + nums[right];
                match s.cmp(&0i32) {
                    Ordering::Less => left += 1usize,
                    Ordering::Greater => right -= 1usize,
                    _ => {
                        let to_push: Vec<i32> = vec![nums[i], nums[left], nums[right]];
                        if res.is_empty() || Some(&to_push) != res.last() {
                            res.push(to_push);
                        }
                        left += 1usize;
                        right -= 1usize;
                    }
                }
            }
        }
        res
    }
}

}