leetcode15-三数之和

原题

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

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

示例:

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

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

解法

思想

三指针,先对数组进行排序,既有助于组合去重,也可以将问题简化。第一个指针确定后,剩下的问题变成leetcode167-两数之和II-输入有序数组的问题。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums==null|| nums.length<3){
            return result;
        }
        Arrays.sort(nums);
        //第一个指针的移动范围
        for(int i=0;i<nums.length-2;i++){
            if(nums[i]>0) return result;
            // 对已经出现过的数字直接跳过 不再进行处理
            if(i!=0 && nums[i] == nums[i-1]) continue;
            int second = i+1; // 从当前位置开始
            int third = nums.length-1; // 从尾部开始
            while(second<third){
               int sum = -(nums[second] + nums[third]);
               if(sum == nums[i]){ // 找到该数组
                    result.add(Arrays.asList(nums[i],nums[second],nums[third]));
                    //跳过相同的元素
                    while(second<third && nums[second] == nums[second+1]) second++;
                    while(second<third && nums[third] == nums[third-1]) third--;
               }
               if(sum <= nums[i]) third--;
               else second++;
            }
        }
        return result;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode15-%e4%b8%89%e6%95%b0%e4%b9%8b%e5%92%8c/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月3日 22:14
下一篇 2020年5月4日

相关推荐

  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0690
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0380
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0110
  • leetcode81-搜索旋转排序数组II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定…

    算法 2020年5月30日
    060
  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0300
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode106-从中序与后序遍历序列构造二叉树

    原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor…

    算法 2020年1月13日
    0380
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    090
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130

发表回复

登录后才能评论