LeetCode之 15. 3Sum

LeetCode之 15. 3Sum

开始刷LeetCode有一小段时间了，决定写一个专辑来加深理解，更方便日后查看。

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

题目大致意思，给定一个整形数组，找到数组中所有唯一的三元组，其总和为零。
注意：不能有重复的三元组。

简单分析一下：

• 首先需要对给定数组进行排序
• 减少无意义的循环
• 避免出现重复的三元组

代码如下：

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (nums == null && nums.length < 3)
            return resultList;
        Arrays.sort(nums);
        int length = nums.length;
        for (int i=0; i<length-2; i++) {
            if (nums[i] > 0)
                break;
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            int left = i+1;
            int right = length-1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ArrayList<Integer> triple = new ArrayList<>();
                    triple.add(nums[i]);
                    triple.add(nums[left]);
                    triple.add(nums[right]);
                    resultList.add(triple);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1])
                        left++;
                    while (left < right && nums[right] == nums[right+1])
                        right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return resultList;
    }

分析：先对数组排序，时间复杂度为O(log(n))，初始化初始位置，查找另外俩个数组元素和等于-nums[i]的组合，从俩边往中间走，结果大于零右边向左移一位，小于零则左边向右移一位，时间复杂度为O(n^2)。 所以时间复杂度为O(n^2)。