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
}
}