Leetcode No.15 ThreeSum

题目解题思路代码示例

题目

原题传送门

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

解题思路

习惯固定一个最小数，在从剩余的数中找次大值和最大值，依次求和，看是否符合固定值value 因此，为了不漏不重，我们先把数组排序

排序 这里用到C# 自带的array.sort() 算法，官方说明 array.sort() 是insertionSort, quickSort, HeapSort 等的混合，平均O( nlogn )

遍历找nums中符合条件的元素

通过在数组nums中定位元素的下标index { small, middle, big}，找到对应元素，并添加进result里

最外层for 遍历small, 内层根据所求sum, 更新middle和big:

当sum == value, middle++, big–， 且同时跳过nums中相同的元素

当sum < value, middle++，同时跳过nums中相同的元素 （注意middle必须要++，否则会死循环！）

当sum > value, big- -，同时跳过nums中相同的元素

代码示例

Leetcode显示 88 / 318 个通过测试用例，还需查错

public IList<IList<int> > ThreeSum(int[] nums) { //result IList<IList<int>> result = new List<IList<int>>(); //分配List<IList<int>>类型大小的存储空间，给并初始化(ref类型初始null, 值value类型为0) //null表示有内存空间，但没有存value；声明是既没空间也没有value; Ilist<int> 类型是为了简化List类的功能的接口 //condition: //condition1: nums < 3 if (nums == null || nums.Length < 3) return result; //return null Array.Sort(nums); //sort for(int small = 0; small < nums.Length - 2; small++) { //condition1: nums[small] repetitive, leap while (small > 0 && small < nums.Length - 2 && (nums[small] == nums[small - 1])) small++; //condition2: nums[small] > 0 if (nums[small] > 0) return result; int middle = small + 1, big = nums.Length - 1; while( middle < big) { int sum = nums[small] + nums[middle] + nums[big]; //condition3: find if (sum == 0) { result.Add(new List<int>() { nums[small], nums[middle], nums[big] }); //create List<int> and add into result(IList) while (middle < big && (nums[middle] == nums[++middle])) middle++; //increase middle and try to find while (middle < big && (nums[big] == nums[--big])) big--; //decrease big and try to find } //condition4: less than else if (sum < 0) { //increase middle and try to find bigger middle (uniquify!) while (middle < big && (nums[middle] == nums[++middle])) middle++; } //condition5: more than else if (sum > 0) { //decrease big and try to find smaller big while (middle < big && (nums[big] == nums[--big])) big--; //find smaller big } } }