-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
53 lines (52 loc) · 2.33 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//思路为遍历数组的每一个数,固定住当前数,找出这个数以后的两个数和这个数相加为0。
//先对数组排序,保证后面数不小于前面数。
//创建current代表当前遍历到的数字,初始值设为1.
//遍历数组,如果当前数大于0,则停止循环,后面一定没有数能和他加和为0。如果当前数和上一轮遍历的数字相同,则跳过该次遍历。
//设置left代表当前数下一个数,right代表数组尾端数字。将current设为当前数。
//在left小于right的条件下遍历当前数右面的数组,如果current与left和right指向的数之和为0,则将三个数字计入结果。
//同时在left小于right的条件下,使left向右移动,right向左移动。直到left和right分别指向和之前不同的值。
//如果current与left和right指向的数之和小于0,则使left向右移动找到更大的值。
//如果current与left和right指向的数之和大于0,则使right向左移动找到更小的值。
using System;
using System.Collections.Generic;
namespace _3Sum
{
class Program
{
static void Main(string[] args)
{
int[] nums = { 1, -2, -3, 4, 1, 3, 0, 3, -2, 1, -2, 2, -1, 1, -5, 4, -3 };
ThreeSum(nums);
}
static IList<IList<int>> ThreeSum(int[] nums)
{
var res = new List<IList<int>>();
if (nums.Length == 0) return res;
Array.Sort(nums);
int lastOne = nums[0] - 1;
for (int i = 0; i < nums.Length - 2; i++)
{
if (nums[i] == lastOne) continue;
int target = -nums[i];
int li = i + 1, hi = nums.Length - 1;
while (li < hi)
{
if (nums[li] + nums[hi] < target)
li++;
else if (nums[li] + nums[hi] > target)
hi--;
else
{
var last = nums[li];
res.Add(new List<int> { nums[i], nums[li], nums[hi] });
lastOne = nums[i];
while (li < hi && nums[li] == last)
li++;
hi--;
}
}
}
return res;
}
}
}