首页 > 编程语言 >今日算法随笔:三数之和

今日算法随笔:三数之和

时间:2024-09-05 10:40:52浏览次数:10  
标签:排序 nums 重复 三数 三元组 算法 数组 随笔 指针

题目链接:15. 三数之和

思路

排序 + 双指针

采用 排序 + 双指针 的方法来解决三数之和问题。首先对数组进行排序,然后通过双指针法,针对每一个固定的元素,从其后的数组部分寻找符合条件的三元组。这样能够避免重复的三元组,且利用排序的性质来优化查找效率。

解题过程

方法运用

  1. 排序数组:首先将数组 nums 进行升序排序,这样可以方便使用双指针法,同时也能跳过重复的元素,避免重复的三元组。
  2. 遍历数组:从第一个元素开始,依次固定一个数 nums[i],然后使用双指针法在 i+1 到数组末尾之间查找两个数 nums[l]nums[r],使得三者之和为 0
    • 如果三者之和等于 0,将该三元组加入结果集。
    • 如果三者之和小于 0,左指针右移以增大和。
    • 如果三者之和大于 0,右指针左移以减小和。
  3. 跳过重复元素:为了避免重复的三元组,在遍历过程中跳过相邻相同的元素,并在更新指针时跳过重复的 nums[l]nums[r]

复杂度

  • 时间复杂度: $O(n^2)$,排序的时间复杂度为 $O(n \log n)$,而双指针的查找过程在最坏情况下为 $O(n^2)$,因此总的时间复杂度为 $O(n^2)$。
  • 空间复杂度: $O(1)$,除了存储结果的空间外,算法的空间开销主要用于排序,排序可以在原数组上进行,因此不需要额外空间。

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 存储结果的列表
        List<List<Integer>> res = new ArrayList<>();
        // 对数组进行排序
        Arrays.sort(nums);
        int n = nums.length;

        // 遍历数组
        for (int i = 0; i < n - 2; i++) {
            // 跳过重复的第一个数字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 双指针查找
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];

                if (sum == 0) {
                    // 找到三元组,加入结果集
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    
                    // 跳过重复的左边元素
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    // 跳过重复的右边元素
                    while (l < r && nums[r] == nums[r - 1]) r--;

                    // 移动双指针
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;  // 左指针右移
                } else {
                    r--;  // 右指针左移
                }
            }
        }
        
        return res;
    }
}

标签:排序,nums,重复,三数,三元组,算法,数组,随笔,指针
From: https://www.cnblogs.com/yubaibaibubai/p/18397875

相关文章

  • 数模国赛冲刺 | 预测类创新算法CNN-GRU、CNN-LSTM、CNN-BiGRU、CNN-BiLSTM、CNN-BiGRU
    ​预测算法——CNN-GRU、LSTM、BiGRU、BiLSTM-Attention本文汇总了基于卷积神经网络(CNN)与循环神经网络(RNN)及其变体(如GRU、LSTM、BiGRU、BiLSTM)组合的多种预测算法,深入探讨了这些算法的原理、结构、优缺点以及实际应用场景。此外,本文特别介绍了结合Attention机制的CNN-RNN组合......
  • Nature Communications 单细胞算法 scDist,教你怎么找到重要的细胞亚群与基因!
    生信碱移scDist: 寻找关键细胞亚群与基因的方法单细胞RNA测序(scRNA-seq)使我们能够研究受药物治疗、感染以及癌症等疾病中关键的细胞亚群。为了找到可能影响疾病的细胞亚群乃至基因,我们常常去比较两个或多个组之间显著差异的细胞类型。这里"显著差异"的定义可以是不同方面的,......
  • 无刷电机控制算法的演变
    一,无刷电机可控制方式的演变1.霍尔有感六步换相不管是方波控制还是正弦波控制,六步换相驱动方法都是最简单的无刷电机驱动方式,驱动原理同有刷电机的驱动方式,只是普通无刷电机为3相六相位,普通有刷电机为单相两相位。只需要在合适的时间使能对应的相位矢量,电机便能正常运转。只要换......
  • 【自动驾驶】控制算法(八)横向控制Ⅰ | 算法与流程
    写在前面:......
  • 有向图最短路径与BFS算法的研究
    有向图最短路径与BFS算法的研究引言有向图G=(V,E)的定义与例子BFS算法及其局限性特定边集E'的构造确认最短路径实现BFS并验证结果(C代码)引言在图论中,寻找最短路径是一个经典问题。广度优先搜索(BFS)是一种在无权重图(即所有边的权重相同)中找到从源节点到所有其他......
  • 有向图的最短路径与BFS算法的局限性分析
    有向图的最短路径与BFS算法的局限性分析引言有向图G=(V,E)的示例图G的邻接表表示问题描述BFS算法回顾BFS在示例图G中的应用及局限性构造E_s并证明BFS的局限性C语言实现及验证分析C语言实现的BFS算法结论引言在图论中,最短路径问题是寻找从一个结点(源结点)到......
  • 解决职业摔跤手分类问题的算法与实现
    解决职业摔跤手分类问题的算法与实现引言问题定义算法设计二分图判定算法步骤伪代码C语言实现引言在职业摔跤界,摔跤手通常被分为“娃娃脸”(“好人”)型和“高跟鞋”(“坏人”)型。在任意一对摔跤手之间,都有可能存在竞争关系。本文的目标是设计一个算法,用于判断......
  • 狐狸算法(FOX)优化BP神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2FOX主函数代码3.3FOX-BP4视频讲解0引言狐狸算法(Foxoptimizer,FOX)是由HardiMohammed在2023年提出群智能算法,该算法模拟了自然界中狐狸在捕猎时的觅食。FOX基于测量狐狸和猎物之间的距离来执行有效的跳......
  • 狐狸算法(FOX)优化支持向量机原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2FOX主函数代码3.3FOX-SVM4视频讲解0引言狐狸算法(Foxoptimizer,FOX)是由HardiMohammed在2023年提出群智能算法,该算法模拟了自然界中狐狸在捕猎时的觅食。FOX基于测量狐狸和猎物之间的距离来执行有效的跳......
  • 狐狸算法(FOX)优化长短期记忆神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2FOX主函数代码3.3FOX-LSTM4视频讲解0引言狐狸算法(Foxoptimizer,FOX)是由HardiMohammed在2023年提出群智能算法,该算法模拟了自然界中狐狸在捕猎时的觅食。FOX基于测量狐狸和猎物之间的距离来执行有效的......