LeetCode-15 三数之和

用户3470542

发布于 2019-06-26 17:48:46

8500

发布于 2019-06-26 17:48:46

文章被收录于专栏：算法半岛算法半岛

> 题目：15. 三数之和

> 难度：中等

> 分类：字符串

> 解决方案：双指针

今天我们学习第15题三数之和，这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

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

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

示例：

例如, 给定数组nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[  [-1, 0, 1],  [-1, -1, 2]]

分析

我们做过LeetCode-1 两数之和，这个题目与它有联系，但也有蛮大的差异。像这样求和的问题我们首先想到的是暴力求解方法，这个题目用暴力求解的时间复杂度为 O(n^3)。我们想一想能不能将时间按复杂度降到 O(n^2)？

先将数组进行排序(排序函数的时间复杂度为 O(nlgn))，然后我们就可以对这个有序数组用双指针的方法从左右两边向中间扫描了：

对于有序数组的两数之和，我们就是找到左右指针指向的数之和等于 target就可以了；
对于有序数组的三数之和，我们可以先固定一个数(即为 target)，然后就是找到左右指针指向的数之和等于 target就可以了。

对题目描述中示例进行分析如下图所示：

在遍历查找过程中有几点需要值得注意的：

题目要求答案中不可以包含重复的三元组，因此需要去重处理
由于数组已排序，当固定数字大于零(即为 target>0)时,则它后面的数都大于零，不需要继续查找

java代码如下所示：

class Solution {   // 存储满足条件的三元组    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums){
        if(nums == null || nums.length < 3)            return res;        // 给数组排序        Arrays.sort(nums);
        int len = nums.length;
        // 注意遍历的右边界条件        for (int i=0; i<len-2; i++){            // 去掉重复值            if (i > 0 && nums[i] == nums[i-1])                continue;
            // 由于数组已排序，当nums[i]>0,则它后面的数都大于零，不需要继续查找            if (nums[i] > 0)                break;
            // 在数组中查找两个数与nums[i]的和为0, i+1表示左指针，len-1表示右指针，nums[i]表示固定数target            find(nums, i+1, len-1, nums[i]);        }
        return res;    }
    // 查找函数    private void find(int[] nums, int begin, int end, int target){        int left = begin, right = end;        while (left < right){            // 查找满足条件的三个            if(nums[left] + nums[right] + target == 0){                // 保存这个三个数                List<Integer> tmp = new ArrayList<>();                tmp.add(target);                tmp.add(nums[left]);                tmp.add(nums[right]);                res.add(tmp);
                // 去掉重复的值                while (left < right && nums[left] == nums[left+1])                    left++;                while (left < right && nums[right] == nums[right-1])                    right--;
                // 移动左右指针                left++;                right--;            }else if(nums[left] + nums[right] + target < 0){    // 当这个三个之和小于0，则左指针向右移动                left++;            }else { // 当这三个数大于零，则右指针向左移动                right--;            }        }    }}