LeetCode_15 三数之和 (数组题)

题目地址:https://leetcode-cn.com/problems/3sum/

题目:

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

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

示例:

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

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

试题分析:

这道题因为不允许使用暴力3层循环,所以如果没做过的话还是有一定难度的,对编码细节要求比较高,不小心就会出错。这道题和之前做过的两数之和其实思路上类似,也可以采用hashmap来实现, 可以在外层进行一次循环,再在内部循环两数之和等于target-当前外部循环的数值,但是这样会增加n个hashmap(n-1)的空间复杂度,这种解法的核心思路和两数之和查找思路一样,这个方案的时间复杂度为O(n2),空间复杂度为O(n2)。

下面我再介绍一种时间复杂度为O(n^2),但是空间复杂度为O(1)的算法。该算法不是依赖hashmap,而是巧妙的利用了有序数组的夹闭查找算法,因为在有序的数组中可以通过单次顺序查找避免走回头路,通过夹闭查找从两头并行向中间查找,当子循环中的夹闭查找的两个指针相遇则一次子循环结束。

该算法在实现过程中有几个注意点:

1)在循环过程中需要进行重复数的跳过操作;

2)在循环体内需要分3种情况分别进行考虑,a.当前循环三数相加小于目标值,因为内循环数组是从小到大有序的,所以这说明内循环的前值小值加上后值大值是不符合要求的,后值不能后退,那就需要前值继续+1后移,取顺序更大的值;b.当前循环3数相加大于目标值,同理说明后值大值太大了,后值需要前移来取小值才有可能三数相加等于目标值;c.当前循环3数相加等于目标值,同理则表示三数复合要求,则将这3个数创建一个新的List并加到结果集中;

3)在内循环上面3种情况下,还要考虑有连续相等的数值的情况,那就需要在内循环的分支里分别根据3种情况进行下标的前后移动,这样可以减少内循环的次数,加速值查找。

代码:

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        if(nums.length<3){
            return resultList;
        }

        int target = 0;

        //先对数据进行从小到大排序,再进行夹击查找
        Arrays.sort(nums);
        int j,k;
        for(int i=0;i<nums.length-2;i++){
            j = i + 1;
            //跳过重复的数
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            k = nums.length-1;
            while(j<k){
                if(nums[i]+nums[j]+nums[k]<target){
                    j++;//j右移动,取右边大数值
                    while(nums[j]==nums[j-1] && j<k){
                        j++;
                    }
                }else if(nums[i]+nums[j]+nums[k]>target){
                    k--;
                    while(nums[k]==nums[k+1] && j<k){
                        k--;
                    }
                }else{
                    List<Integer> result = new ArrayList<Integer>(3);
                    result.add(nums[i]);
                    result.add(nums[j]);
                    result.add(nums[k]);
                    resultList.add(result);
                    j++;
                    k--;
                    while(nums[j]==nums[j-1] && nums[k]==nums[k+1] && j<k){
                        j++;
                    }
                }
            }
        }
        return resultList;
    }

源码路径:com.monkey01.array.ThreeSum_15

配套测试代码路径:test目录com.monkey01.array.ThreeSum_15Test

https://github.com/feiweiwei/LeetCode4Java.git

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 原文地址:http://theory.stanford.edu/~amitp/GameProgramming/ 1...
    达微阅读 19,690评论 0 28
  • 算法思想贪心思想双指针排序快速选择堆排序桶排序荷兰国旗问题二分查找搜索BFSDFSBacktracking分治动态...
    第六象限阅读 3,339评论 0 0
  • 有家才有梦,有家才有情,有家才有温暖。家是我们依靠的港湾,家是我们一个躲风雨的地方,让疲惫不堪的身心得以修复,家是...
    道悟生人阅读 153评论 0 0
  • 获取位于tableview顶部的section,取所有可见的Cell第一个则为最顶部的,然后根据cell获取ind...
    c5550ea746f8阅读 659评论 0 0
  • 数据库,面向应用,面向事务数据仓库,面向主题,面向分析 数据仓库流程ETLextra transfer load ...
    ___Hello阅读 256评论 0 0