0015.三数之和

方法一：排序 + 双指针

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

func threeSum(nums []int) [][]int {
	ans, n := make([][]int, 0), len(nums)
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		for i > 0 && i < n && nums[i] == nums[i-1] {
			i++
		}
		for j, k := i+1, n-1; j < k; {
			if nums[i]+nums[j]+nums[k] == 0 {
				ans = append(ans, []int{nums[i], nums[j], nums[k]})
				j, k = j+1, k-1
				for j < k && nums[j] == nums[j-1] {
					j++
				}
				for j < k && nums[k+1] == nums[k] {
					k--
				}
			} else if nums[i]+nums[j]+nums[k] > 0 {
				k--
			} else {
				j++
			}
		}
	}
	return ans
}

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