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日

相关推荐

  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入: 6 输出: true 解释: 6 = 2 × 3 示例2: 输入: …

    算法 2020年2月6日
    0120
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0190
  • leetcode450-删除二叉搜索树中的节点

    原题 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一…

    2020年1月16日
    0100
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode154-寻找旋转排序数组中的最小值II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。…

    算法 2020年1月7日
    090
  • leetcode122-买卖股票的最佳时机II

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意: 你不能同…

    算法 2020年2月7日
    080
  • leetcode1095-山脉数组中查找目标值

    原题 (这是一个 交互式问题 ) 给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in…

    算法 2020年4月29日
    0170
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode820-单词的压缩编码

    原题 给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如,如果这个列表是 ["time", "me", "bell"],我们就可以将其表示为 S …

    算法 2020年3月28日
    090
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0150

发表回复

登录后才能评论