【每日算法Day 12】三数之和

题目链接

LeetCode 15. 三数之和 (opens new window)

题目描述

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

示例

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

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

解题思路

如果使用暴力解法，对每一个数，寻找其余数中与其和为0的两个数，时间复杂度为O(n^3)，显然不可取。 对暴力解法进行优化，首先排序数字，从左向右确定第一个数。当第一个数确定后，后面两数的和就确定了，在后面的子数组中分别从左右两侧向中间查找，逐渐缩小范围直至找到符合条件的两个数或者找不到符合条件的数。此时时间复杂度就被缩小到了O(nlogn)+O(n^2)=O(n^2)。

public List<List<Integer>> threeSum(int[] nums) {
    if (nums==null||nums.length<3)
        return new ArrayList<>();
    Arrays.sort(nums);
    if (nums[0]>0)
        return new ArrayList<>();

    List<List<Integer>> lists=new ArrayList<>();
    for (int left = 0; left < nums.length - 2; left++) {
        if (left>0&&nums[left]==nums[left-1]) continue;
        int target=-nums[left];
        int right=nums.length-1;
        for (int mid = left + 1; mid < nums.length - 1; mid++) {
            if (mid>left+1&& nums[mid]==nums[mid-1]) continue;
            while (mid < right && nums[mid] + nums[right] > target) {
                --right;
            }
            if (mid==right) break;
            if (nums[mid] + nums[right] == target) {
                List<Integer> list=new ArrayList<>();
                list.add(nums[left]);
                list.add(nums[mid]);
                list.add(nums[right]);
                lists.add(list);
            }
        }

    }
    return lists;
}