18. 四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。

解题思路

有两个坑：

• 首先是n < 4的情况是存在的
• 其次四个数的加和可以超过i32的最大值

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum(mut v: Vec<i32>, t: i32) -> Vec<Vec<i32>> {
        v.sort();
        let n = v.len();
        let mut res = vec![];
        if n < 4 { return res }
        for i in 0..n-3 {
            if i > 0 && v[i] == v[i-1] { continue }
            for l in (i+3..n).rev() {
                if l < n - 1 && v[l] == v[l+1] { continue }
                let mut j = i + 1;
                let mut k = l - 1;
                while j < k {
                    if v[i] as isize + v[j] as isize + v[k] as isize + v[l] as isize == t as isize {
                        res.push(vec![v[i], v[j], v[k], v[l]]);
                        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[i] as isize + v[j] as isize + v[k] as isize + v[l] as isize) < t as isize {
                        j += 1;
                    } else {
                        k -= 1;
                    }
                }
            }
        }
        res
    }
}
}

学习感想