C#LeetCode刷题之#15-三数之和（3Sum）

问题

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

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.

Note:The solution set must not contain duplicate triplets.

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

示例

public class Program {

    public static void Main(string[] args) {
        var intervals = new int[] { -1, 0, 1, 2, -1, -4 };

        var res = ThreeSum(intervals);
        ShowArray(res);

        intervals = new int[] { 0, 0, 0 };

        res = ThreeSum2(intervals);
        ShowArray(res);

        Console.ReadKey();
    }

    private static void ShowArray(IList<IList<int>> list) {
        foreach(var nums in list) {
            foreach(var num in nums) {
                Console.Write($"{num} ");
            }
            Console.WriteLine();
        }
    }

    public static IList<IList<int>> ThreeSum(int[] nums) {
        //暴力解法肯定超时无法AC
        var res = new List<IList<int>>();
        for(int i = 0; i < nums.Length; i++) {
            for(int j = 0; j < nums.Length; j++) {
                for(int k = 0; k < nums.Length; k++) {
                    if(nums[i] + nums[j] + nums[k] == 0 &&
                    i != j && j != k && k != i) {
                        var line = new List<int> { nums[i], nums[j], nums[k] };
                        line = line.OrderBy(r => r).ToList();
                        if(!res.Any(l => l[0] == line[0] &&
                        l[1] == line[1] &&
                        l[2] == line[2])) {
                            res.Add(line);
                        }
                    }
                }
            }
        }
        return res;
    }

    public static IList<IList<int>> ThreeSum2(int[] nums) {
    	//先固定 i，再计算三数之和是不是0
    	//需认真分析是否有重复的三元组
        var res = new List<IList<int>>();
        var length = nums.Length;
        Array.Sort(nums);
        for(var i = 0; i < length - 2; i++) {
            //定义左右指针j和k
            //i为循环变量，可以认为先固定了i
            var j = i + 1;
            var k = length - 1;
            //分析j和k
            while(j < k) {
            	//若和大于0，则需要减整体的值，将右指针 k 减1
                if(nums[i] + nums[j] + nums[k] > 0) k--;
                //若和小于0，则需要加整体的值，将左指针 j 加1
                else if(nums[i] + nums[j] + nums[k] < 0) j++;
                else {
                	//若和正好等于0，将其存放进结果中
                	//然后需要处理重复三元组的情况
                	//不重复三元组需要3个索引各不相同并且组成的值的结果不能重复
                	//以下3个条件组成了满足不重复三元组的所有条件
                	//条件1：i、j、k的顺序具有稳定性，总是从小到大
                    res.Add(new int[] { nums[i], nums[j], nums[k] });
                    //首先使用 j + 1 <= nums.Length - 1 保证数组不越界
                    //条件2：再向右找到第1个值不和当前左指针相同的值的索引
                    //若为 1，1，1，1，1，2，找到2
                    while(j + 1 <= nums.Length - 1 && nums[j + 1] == nums[j++]) { }
                }
            }
            //条件3：向右找到最后1个和当前被固定的 i 的值相同的值的索引
            //若为 1，1，1，1，1，2，找到2前面的最后一个1
            while(i + 1 <= nums.Length - 1 && nums[i + 1] == nums[i]) i++;
        }
        return res;
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

-1 0 1
-1 -1 2
0 0 0

分析

显而易见， ThreeSum 的时间复杂度为： O(n^3)O(n3)，ThreeSum2 的时间复杂度为：O(n^2)O(n2) 。