Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

三数之和

发表于 2020-04-15 | 分类于 算法题 | 0 | 阅读次数 119

题目:三数之和

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

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

例如 :
输入:[-1, 0, 1, 2, -1, -4],
输出:[[-1, 0, 1],[-1, -1, 2]]

解题思路:

  1. 对给定的数组排序,再使用双指针找出与当前数相加和为0的数
  2. 对于已经排序的数组而言,在0之和不会再有与之相加和为0的两个数
  3. 在遍历中,应判断当前数、左指针和右指针的下一位是否与当前相等,避免出现重复解

题解代码如下:

class Solution {
    private List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == nums || nums.length < 3) {
            return result;
        }
        // 排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int temp = nums[i];
            // 对于当前已排好序的数组来说,0后面的数字不可能出现三个数相加等于0
            if (temp > 0) {
                return result;
            }
            // 跳过重复元素,可以避免出现重复解
            if (i > 0 && temp == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int leftNum = nums[left];
                int rightNum = nums[right];
                int sum = temp + leftNum + rightNum;
                if (sum == 0) {
                    result.add(Arrays.asList(temp, leftNum, rightNum));
                    // 如果当前左指针与右指针是否和下一位相同,去除重复解
                    while (left < right && leftNum == nums[left + 1]) {
                        left ++;
                    }
                    while (left < right && rightNum == nums[right - 1]) {
                        right --;
                    }
                    left ++;
                    right --;
                } else if (sum < 0) {
                    left ++;
                } else {
                    right --;
                }
            }
        }
        return result;
    }
}
# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
最长公共前缀
电话号码中的字母组合
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号