[Java·算法·中等] LeetCode15. 三数之和

简介: [Java·算法·中等] LeetCode15. 三数之和

 

题目

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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


示例

示例1

输入:nums = [-1,0,1,2,-1,-4]

输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意,输出的顺序和三元组的顺序并不重要。


示例2

输入:nums = [0,1,1]

输出:[]

解释:唯一可能的三元组和不为 0 。


示例3

输入:nums = [0,0,0]

输出:[[0,0,0]]

解释:唯一可能的三元组和为 0


提示

👉️ 力扣原文

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k=0;k<nums.length - 2;k++){
            if(nums[k] > 0) break;
            if(k>0 && nums[k] == nums[k-1]) continue;
            int i=k+1,j=nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] +nums[j];
                if(sum < 0){
                    while(i<j && nums[i] == nums[++i]);
                }else if(sum>0){
                    while(i < j && nums[j] == nums[--j]);
                }else{
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}


详细解读

让我解释一下代码的主要逻辑:


  1. 首先,对给定的整数数组进行排序,这是为了方便后续的处理,使得相同元素在一起,并且方便进行指针移动来遍历可能的三元组。
  2. 然后,使用三个指针,其中一个指向当前处理的元素(k),另外两个分别指向当前元素的下一个(i)和数组末尾(j)。
  3. 在循环中,首先判断当前元素是否大于零,若是,则直接跳出循环,因为后面的元素都是正数,无法组成三元组使得和为零。
  4. 如果当前元素不是第一个元素,并且与前一个元素相同,则跳过该元素,以避免重复计算。
  5. 然后,在内部的 while 循环中,通过不断移动 i 和 j 指针,逐步向中间靠拢,同时判断三个元素之和与零的关系:
  1. 若和小于零,则移动 i 指针直到找到一个不同的值;
  2. 若和大于零,则移动 j 指针直到找到一个不同的值;
  3. 若和等于零,则将这个三元组加入结果集中,并继续移动 i 和 j 指针直到找到不同的值。
  1. 最后,返回结果集。


这段代码的时间复杂度为 O(n^2),其中 n 是数组的长度。因为在循环中,i 和 j 指针分别最多遍历一次整个数组。

相关文章
|
17天前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
11天前
|
搜索推荐 算法 Java
手写快排:教你用Java写出高效排序算法!
快速排序(QuickSort)是经典的排序算法之一,基于分治思想,平均时间复杂度为O(n log n),广泛应用于各种场合。在这篇文章中,我们将手写一个Java版本的快速排序,从基础实现到优化策略,并逐步解析代码背后的逻辑。
26 1
|
1天前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
|
9天前
|
安全 算法 Java
java系列之~~网络通信安全 非对称加密算法的介绍说明
这篇文章介绍了非对称加密算法,包括其定义、加密解密过程、数字签名功能,以及与对称加密算法的比较,并解释了非对称加密在网络安全中的应用,特别是在公钥基础设施和信任网络中的重要性。
|
17天前
|
搜索推荐 算法 Java
经典排序算法之-----选择排序(Java实现)
这篇文章通过Java代码示例详细解释了选择排序算法的实现过程,包括算法的基本思想、核心代码、辅助函数以及测试结果,展示了如何通过选择排序对数组进行升序排列。
经典排序算法之-----选择排序(Java实现)
|
18天前
|
搜索推荐 算法 Java
|
22天前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
37 2
|
22天前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
33 1
|
10天前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
11 0
|
15天前
|
算法 Java
HanLP — HMM隐马尔可夫模型 -- 维特比(Viterbi)算法 --示例代码 - Java
HanLP — HMM隐马尔可夫模型 -- 维特比(Viterbi)算法 --示例代码 - Java
23 0

热门文章

最新文章

下一篇
云函数