草庐IT

LeetCode - 三数之和

程序员翔仔 2023-03-28 原文

题目信息

源地址：三数之和

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

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

提示信息

示例 1

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

示例 2

输入：nums = []
输出：[]

示例 3

输入：nums = [0]
输出：[]

限制

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

实现逻辑

暴力枚举

最先想到的应该是暴力枚举的方法，当然这也是最简单的的方法。

既然这里要找出符合要求的三个数，当然是使用三层循环依次去匹配，缺点就是时间复杂度达到了 \(O(n^3)\)，当数组长度特别长的时候，程序运行时间也会特别长。

哈希匹配

从“两数之和”题目中可以知道，使用哈希表结构采用空间换时间的方式，时间复杂度能从 \(O(n^2)\) 降到了 \(O(n)\)。

如果将这种空间换时间的方式代入这个题目，可以将暴力破解 \(O(n^3)\) 的时间复杂度降到 \(O(n^2)\)，这也是一个非常大的提升。

排序 + 双指针

现在思考一下如何将时间复杂度从 \(O(n^2)\) 降下去。

  1. 首先一层循环是必不可少的，因为至少要对给定的数组做一次枚举；
  2. 假如拿到数组的第一个元素，需要思考一下怎么从数组剩下的元素中找到匹配的两个元素，换一个思路其实就是从剩下的数组元素中找到和等于第一个元素相反数的两个元素，所以这里退变成了“两数之和”的逻辑；
  3. 如果对剩下的元素采用哈希匹配的方法，其实就和上面的方法一致了，由于答案中不可以包含重复的三元组，这里先对数组进行排序，方便后续跳过相同的答案，再采用数组首尾双指针的方法查找匹配的两个数。
package cn.fatedeity.algorithm.leetcode;

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

public class ThreeSum {
    public List<List<Integer>> answer(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                // 答案不可以包含重复的三元组，这里相同的数直接过掉
                continue;
            }
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int diff = target - (nums[left] + nums[right]);
                if (diff > 0) {
                    left++;
                } else if (diff < 0) {
                    right--;
                } else {
                    boolean leftFlag = left == 0 || nums[left] != nums[left - 1];
                    boolean rightFlag = right == nums.length - 1 || nums[right] != nums[right + 1];
                    if (leftFlag || rightFlag) {
                        // 这里的 if 判断仍然是避免答案出现重复的三元组
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        result.add(list);
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

使用这个方式解决这个题目，耗时的地方有两个：对原数组进行排序；对排序后的数组查找出和为目标数的两个数。

排序的时间复杂度可以看做是 \(O(n\log_2n)\)，查找出剩余两个数采用了遍历数组并嵌套使用双指针遍历，时间复杂度为 \(O(n \times n)\)，最终总体的时间复杂度在 \(O(n^2)\)。

在整个过程当中，除了存储答案需要额外的空间，实际的空间复杂度是 \(O(1)\)。

之和LeetCodecodenumsspan算法与数据结构

有关LeetCode - 三数之和的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  3. ruby - 在 Ruby 中将两个数组相乘并获得相乘值之和的有效方法是什么？ - 2

    在Ruby中将两个数组相乘并获得相乘值之和的有效方法是什么？我在Ruby中有两个数组:array_A=[1,2,1,4,5,3,2,6,5,8,9]array_B=[3,2,4,2,5,1,3,3,7,5,4]我的目标是获取array_A*array_B的总和值，即1*3+2*2+1*4+...+8*5+9*4。因为我需要在我的应用程序中对它们进行数百万次计算，进行此类计算的最有效方法是什么？这就像矩阵计算:1*N矩阵*N*1矩阵或向量点积。 最佳答案 更新我刚刚根据新评论更新了基准。正在关注Joshua'scomment，注入(i

  4. 【算法题解】20. 两数之和 - 2

    这是一道简单题题目来自：https://leetcode.cn/problems/two-sum/题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。提示：22nums.length104−109−109nums[i]109−109−109target109只会存在一个有效答案进阶：你可以想出一个时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？示例1：输入：nums=[2,7,11,15],targe

  5. LeetCode——2347. 最好的扑克手牌 - 2

    一、题目给你一个整数数组ranks和一个字符数组suit。你有5张扑克牌，第i张牌大小为ranks[i]，花色为suits[i]。下述是从好到坏你可能持有的手牌类型：“Flush”：同花，五张相同花色的扑克牌。“ThreeofaKind”：三条，有3张大小相同的扑克牌。“Pair”：对子，两张大小一样的扑克牌。“HighCard”：高牌，五张大小互不相同的扑克牌。请你返回一个字符串，表示给定的5张牌中，你能组成的最好手牌类型。注意：返回的字符串大小写需与题目描述相同。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-poker-hand/d

  6. javascript - 在 JavaScript 中不使用循环求连续整数之和 - 2

    我正在寻找一种方法来进行如下计算:functionsumIntegerUpTo(number){return1+2+3+...+number;}如果您将number作为5传递，函数应该返回1+2+3+4+5的总和。我想知道是否可以不使用循环。 最佳答案 当然是!1+2+3+...+n=n*(n+1)/2 关于javascript-在JavaScript中不使用循环求连续整数之和，我们在StackOverflow上找到一个类似的问题： https://stack

  7. LeetCode：344. 反转字符串 - 2

    🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123一、🌱344.反转字符串题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。来源：力扣（LeetCode）难度：简单提示：1s[i]都是ASCII码表中的可打印字符示例1：输入：s=[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]示例2：输入：s=[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”

  8. 【日常系列】LeetCode《28·动态规划3》 - 2

    数据规模->时间复杂度10^8内容二维数组中的路径问题买卖股票的最佳时机lc62【剑指098】【top100】：不同路径https://leetcode.cn/problems/unique-paths/提示：1题目数据保证答案小于等于2*10^9#方案一：dfs+记忆化classSolution:defuniquePaths(self,m:int,n:int)->int:memo=[[-1]*nfor_inrange(m)]defdfs(i,j):ifi==m-1andj==n-1:return1ifi>=morj>=n:return0ifmemo[i][j]!=-1:returnmemo[

  9. javascript - 斐波那契数列 (JS) - 偶数之和 - 2

    我开始了欧拉计划。我在问题2上想出了这个代码来计算高达400万的偶数斐波那契数的总和。代码似乎做了很多我想做的事。运行代码时，我确实看到列出了正确的总和。我真正感到困惑的唯一部分是结果中显示的最后一个数字。这是它显示的内容:JS代码:varprevious=0;varcurrent=1;varsum=0;varnext;for(i=1;i结果:210441887983382143286069625711410891544613732(thisisthenumberiwastryingtoget)=>354224848179262000000(confusedastowhythisnum

  10. javascript - 在分布式环境中拆分数组以找到两个子数组之和之间的最小差异 - 2

    昨天有人问我这个问题。我必须编写代码将数组分成两部分，以使这两部分之和之间的差异最小。这是我写的代码，复杂度O(n)functionsolution(a){letleftSum=0;letrightSum=a.reduce((acc,value)=>acc+value,0);letmin=Math.abs(rightSum-leftSum);a.forEach((item,i)=>{leftSum+=a[i];rightSum-=a[i];consttempMin=Math.abs(rightSum-leftSum);if(tempMin但后来有人问我如果输入数组长度为1000万，我如

随机推荐