AlgoPressAppearance
0015-三数之和
题目描述
https://leetcode.cn/problems/3sum
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
思路 : 暴力循环，超时
三重循环，字典表去重，时间复杂度 O(n^3) 提交会超时
参考代码
csharp
public class Solution {
private string getKey(int a, int b, int c){
int temp;
if(a > b){
temp = a;
a = b;
b = temp;
}
if(a > c){
temp = a;
a = c;
c = temp;
}
if(b > c){
temp = b;
b = c;
c = temp;
}
return a.ToString() + b.ToString() + c.ToString();
}
public IList<IList<int>> ThreeSum(int[] nums) {
Dictionary<string,string> dict = new Dictionary<string,string>();
IList<IList<int>> result = new List<IList<int>>();
for(int i=0; i<nums.Length -2; i++){
for (int j=i+1; j<nums.Length -1; j++){
for(int k=j+1; k<nums.Length; k++){
if(nums[i] + nums[j] + nums[k] == 0){
string key = getKey(nums[i],nums[j],nums[k]);
if(!dict.ContainsKey(key)){
dict.Add(key,"1");
List<int> arr = new List<int>();
arr.Add(nums[i]);
arr.Add(nums[j]);
arr.Add(nums[k]);
result.Add(arr);
}
}
}
}
}
return result;
}
}
思路2：排序+双指针【官方：TODO】
将数组排序
定义三指针，分别为开始指针，结束指针，中间指针
循环数组，固定第一个数[i]
如果 nums[i] + nums[left] + nums[right] > 0 那么 end 前移
如果 nums[i] + nums[left] + nums[right] < 0 那么 mid后移
中间状态 num[left] 从 i+1 移动到 length-1
注意：第一个数字也需要去重
注意：加入结果集去重后， left++, right-- 否则进入死循环
参考代码
csharp
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
for(int i=0; i<nums.Length - 2; i++){
//去掉第一个数字的重复数据
if(i>0 && nums[i] == nums[i-1]){
continue;
}
int left = i + 1;
int right = nums.Length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0){
right--;
}
else if(sum < 0){
left++;
}
else{ //加入结果集
List<int> list = new List<int>(){nums[i],nums[left],nums[right]};
result.Add(list);
//去除重复数字
while(left < right && nums[right-1] == nums[right]){
right--;
}
while(left < right && nums[left+1] == nums[left]){
left++;
}
left++;
right--;
}
}
}
return result;
}
}
思路3，转化为两数之和
- 固定第一个数
- 将后面的计算转化为两数之和
- 注意去除重复的方法 第一个数 和 第二个数处理方式不同
csharp
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
int start = 0;
int end = nums.Length-1;
while(start <= end - 2){
//如果第一个数就大于0，则后面都大于0，直接返回
if(nums[start] > 0){
break;
}
//如果数字已经重复计算过，则直接跳过
if(start > 0 && nums[start] == nums[start-1]){
continue;
}
//确定了第一个数之后，将后面的数作为两数之和处理
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int j=start+1; j<=end; j++){
Console.WriteLine("j={0}",j);
int sum = 0 - nums[start] - nums[j];
if(dict.ContainsKey(sum)){
List<int> arr = new List<int>(){nums[start],dict[sum],nums[j]};
result.Add(arr);
//不能重复计算 第二个数 , 如 测试用例[0,0,0,0]
while(j < nums.Length-1 && nums[j] == nums[j+1]){
j++;
}
}
else{
if(!dict.ContainsKey(nums[j])){
//Console.WriteLine("add:{0}",nums[j]);
dict.Add(nums[j],nums[j]);
}
}
}
start++;
}
return result;
}
}
复习: 需要再次复习写法
csharp
public class Solution {
//要去取重复，先排序，则当前数字只处理一次
//固定第一个数字之后，加入hash表，后续用两数之和和hash表做校验，是否满足条件
//固定第一个数字之后，后面两个指针分别指向开始和最后一个数，依次往内收缩
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
for(int i=0; i < nums.Length; i++){
if(i>0 && nums[i] == nums[i-1]){
//如果发现相同的数字，直接跳过
continue;
}
int target = -nums[i];
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int j = i+1; j<nums.Length; j++){
int key = target - nums[j];
if(dict.ContainsKey(key)){
//加入结果集
List<int> list = new List<int>();
list.Add(nums[i]);
list.Add(key);
list.Add(nums[j]);
result.Add(list);
while(j < nums.Length-1 && nums[j] == nums[j+1]){
//如果发现第二个数字相同，直接跳过
j++;
}
}
else{
if(!dict.ContainsKey(nums[j])){
dict.Add(nums[j],j);
}
}
}
}
return result;
}
}