0015. 三数之和 3Sum
暴力法
直接用多层遍历的方法, 暴力解决问题. 但这个方法的时间复杂度为 O(n^3), 性能也是最差的.
#![allow(unused)] fn main() { // 暴力法 // 这个方法时间复杂度为 O(n^3), 空间复杂度为 O(n) // 计算结果超时 pub fn three_sum1(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut nums = nums; nums.sort(); let len = nums.len(); if len < 3 { return vec![]; } let mut set = HashSet::new(); for i in 0..(len - 2) { for j in (i + 1)..(len - 1) { for k in (j + 1)..len { if nums[i] + nums[j] + nums[k] == 0 { set.insert(vec![nums[i], nums[j], nums[k]]); } } } } set.into_iter().collect() } }
靠拢型双指针
相关的方法介绍可以看这里.
- 先对数组进行排序
- 外层循环遍历整个数组, 然后在内层使靠拢型用双指针, 来快速找到元素组合
- 可以跳过重复的元素
该算法的时间复杂度是 O(n^2), 空间复杂度是 O(n).
Rust
#![allow(unused)] fn main() { // 靠拢型双指针 // 这个方法时间复杂度为 O(n^2), 空间复杂度为 O(1) pub fn three_sum2(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut result = Vec::new(); let len = nums.len(); if len < 3 { return result; } // 先排序 let mut nums = nums; nums.sort_unstable(); // 遍历数组 for i in 0..(len - 2) { let first = nums[i]; // 忽略掉第一个元素大于0的值 if first > 0 { break; } // 跳过重复的元素 if i > 0 && nums[i] == nums[i - 1] { continue; } // 初始化双指针, 分别指向子数组的左右两端. let mut left = i + 1; let mut right = len - 1; // 循环中止的条件是两指针重叠. while left < right { let sum = first + nums[left] + nums[right]; match sum.cmp(&0) { // 移动其中的一个指针 Ordering::Less => left += 1, Ordering::Greater => right -= 1, Ordering::Equal => { // 其和等于0, 找到目标元素. result.push(vec![first, nums[left], nums[right]]); let last_left_val = nums[left]; // 从左右两端分别跳过重复的元素. while left < right && nums[left] == last_left_val { left += 1; } let last_right_val = nums[right]; while left < right && nums[right] == last_right_val { right -= 1; } } } } } result } }
C++
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
class Solution {
public:
// 双指针法
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
// 先对整数数组排序
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
// 最外层, 遍历所有整数
for (size_t i = 0; i < nums.size() - 2; ++i) {
// 如果最小的值都比0大了, 那就不用再检查后面的值
if (nums[i] > 0) {
break;
}
// 可以跳过重复的元素
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
// 初始化双指针
int left = i + 1;
int right = nums.size() - 1;
int first = nums[i];
while (left < right) {
int sum = first + nums[left] + nums[right];
if (sum < 0) {
// 大小了
left += 1;
} else if (sum > 0) {
// 太大了
right -= 1;
} else {
// 等于0
result.push_back({first, nums[left], nums[right]});
// 路过左侧重复的元素
while (left < right && nums[left] == nums[left + 1]) {
left += 1;
}
// 路过右侧重复的元素
while (right > left && nums[right] == nums[right - 1]) {
right -= 1;
}
// 移动双指针, 向中间靠拢
left += 1;
right -= 1;
}
}
}
return result;
}
};
哈稀表
这个方法的性能并不好, 但也算是解决问题的一个思路. 具体做法就是:
- 使用两个字典分别存储大于0, 以及小于0的元素; 同时统计0出现的次数
- 首先如果0存在, 尝试用它作为正负数的分隔, 其组合情况如下:
(负数, 0, 正数)(0, 0, 0)
- 现在考虑非0组合, 可能的组合情况如下:
(负数, 负数, 正数)(负数, 正数, 正数)
- 将所有的组合都添加到一个集合中, 这样就可以用它来去掉重复的组合
这种思路, 也同样可以用于解决 target != 0 的情况.
#![allow(unused)] fn main() { // 哈稀表 pub fn three_sum4(nums: Vec<i32>) -> Vec<Vec<i32>> { // 0出现的次数. let mut zeros = 0; // 使用两个字典分别存储大于0, 以及小于0的元素 let mut negatives = HashMap::new(); let mut positives = HashMap::new(); for &num in &nums { match num.cmp(&0) { Ordering::Less => { negatives .entry(num) .and_modify(|count| *count += 1) .or_insert(1); } Ordering::Equal => zeros += 1, Ordering::Greater => { positives .entry(num) .and_modify(|count| *count += 1) .or_insert(1); } } } // 使用集合来过滤到重复的结果. let mut set = HashSet::new(); // 首先如果0存在, 就用它作为正负数的分隔. if zeros > 0 { for &num in negatives.keys() { if positives.contains_key(&(-num)) { set.insert(vec![num, 0, -num]); } } if zeros > 2 { set.insert(vec![0, 0, 0]); } } // 现在考虑非0组合, 可能的情竞是: // - (负数, 负数, 正数) // - (负数, 正数, 正数) for &negative in negatives.keys() { for &positive in positives.keys() { let expected_num = -(positive + negative); match expected_num.cmp(&0) { Ordering::Less => { if let Some(&count) = negatives.get(&expected_num) { if (count > 1) || negative != expected_num { if negative < expected_num { set.insert(vec![negative, expected_num, positive]); } else { set.insert(vec![expected_num, negative, positive]); } } } } Ordering::Greater => { if let Some(&count) = positives.get(&expected_num) { if (count > 1) || positive != expected_num { if positive < expected_num { set.insert(vec![negative, positive, expected_num]); } else { set.insert(vec![negative, expected_num, positive]); } } } } Ordering::Equal => (), } } } }