Java:如何实现3和?

2024-05-10

我正在研究 3 Sum 来自己实现它,并遇到了以下规则的实现:

给定一个由 n 个整数组成的数组 S,S 中是否存在满足 a + b + c = 0 的元素 a、b、c?查找数组中所有总和为零的唯一三元组。

注意:三元组 (a,b,c) 中的元素必须按非降序排列。 (即,a ≤ b ≤ c) 解决方案集不得包含重复的三元组。

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

和实现(对数组进行排序,遍历列表,并使用另外两个指针来接近目标):

import java.util.*;

public class ThreeSum {
    List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new LinkedList<>(); 
        
        for (int i=0; i<num.length-2; i++) {
            if (i==0 || (i>0 && num[i] != num[i-1])) { //HERE
                int lo = i+1;
                int hi = num.length-1;
                int sum = 0 - num[i];
                
                while (lo < hi) {
                    if (num[lo] + num[hi] == sum) {
                        res.add(Arrays.asList(num[i], num[lo], num[hi]));
                        while (lo < hi && num[lo] == num[lo+1]) lo++; //HERE
                        while (lo < hi && num[hi] == num[hi-1]) hi--; //HERE
                        lo++; hi--;
                        
                    } else if (num[lo] + num[hi] < sum) lo++;
                    else hi--; 
               }
            }
        }
        
        return res;
    }
    
    //Driver
    public static void main(String args[]) {
        ThreeSum ts = new ThreeSum();
        int[] sum = {-1, 0, 1, 2, -1, -4};
        
        System.out.println(ts.threeSum(sum));
    }
}

我的问题是(位于评论位置://此处),检查的原因是什么num[i] != num[i-1], num[lo] == num[lo+1], and num[hi] == num[hi-1]?据说他们应该跳过相同的结果,但这意味着什么?例子确实会有帮助。

预先感谢您,并将接受回答/赞成票。


想象一下你有{-1,-1,0,1,2,4}并考虑三元组 num[0]、num[2]、num[3] (-1,0,1)。

lo=0这里。要排除具有相同值的三元组 num[1]、num[2]、num[3],我们应该递增lo并跳过重复项

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Java:如何实现3和? 的相关文章

随机推荐

  • Task.Factory.StartNew 与异步方法

    可能是一个微不足道的问题 但它可能有助于我的基本理解 以下两个实现之间有什么重要区别吗 Task Factory StartNew public Task
  • Arduino Nano 33 IoT 的软件序列号

    我计划从旧的 5V Arduino Nano 迁移到新的 Arduino Nano 33 IoT 我已经使用软件串行 SoftwareSerial h 为旧的 5V Arduino Nano 编写了一个功能代码 以便与 Sim800L 模块
  • Gremlin 中的广度优先枚举

    我正在尝试使用 Gremlin 进行广度优先枚举 但是我无法找到一种方法来输出枚举期间观察到的所有步骤 我只能打印出最后一次迭代的结果 我的问题是 给定这样的起始节点 我如何使用 Gremlin 跟踪所有路径 不知道整体深度 并打印出我沿途
  • 如何在javafx中获取当前屏幕详细信息?

    我的电脑连接了多个显示器 从 javaFX 我可以获得主屏幕 但我需要了解当前舞台所在屏幕的屏幕详细信息 我怎样才能得到它 尝试使用获取矩形屏幕 http docs oracle com javafx 2 api javafx stage
  • 如何在 plt.show() 之后保持脚本运行[重复]

    这个问题在这里已经有答案了 之后plt show 我只想继续 但需要关闭弹出图 我该怎么做才能跳过该操作 这是我的代码 plt show time sleep 1 plt close all 其他代码 还有一个关于如何最大化数字制作的问题p
  • SQL*Loader - 如何忽略具有特定字符的某些行

    如果我有一个以下格式的 CSV 文件 fd sdf dsfds dsfd fd asdf dsfds dsfd fd sdf rdsfds dsfd fdd sdf dsfds fdsfd fd sdf dsfds dsfd fd sdf
  • 使用 TensorFlow 2.1 的 Cloud TPU v3 Pod 的 TPUClusterResolver 出现错误

    我正在尝试在带有 TensorFlow 2 1 的 Google Cloud Compute Engine VM 上使用我的 抢占式 Cloud TPU v3 256 但它似乎无法正常工作TPUClusterResolver抛出一个Coul
  • 使用 TCPDF PHP 库横向显示的图像

    我正在使用 TCPDF PHP 库生成包含照片的 PDF 文档 由于某种原因 某些照片在我的计算机和网络上正确显示 但当我将该图像放入 PDF 中时 它似乎是横向的 这只发生在某些图像上 大多数图像显示正确 下面是在 PDF 中横向显示的示
  • 如何在 Laravel 5.4 中使用 bootstrap 4?

    我在我的 laravel 应用程序上使用 npm 安装了 bootstrap 4 但我认为 bootstrap 3 的工作落后于 bootstrap 4 使用命令 npm install npm install email protecte
  • 使用 imagettftext 字体时出现问题

    这是当我更改有效网站的环境时收到的错误消息 Warning imagettftext function imagettftext Could not find open font 首先我以为这是因为缺乏文件权限 但事实并非如此 我检查了路径
  • 创建用于存储高尔夫球成绩的可扩展数据库架构

    我正在尝试设计一个数据库来存储我所有的朋友和我的高尔夫球成绩 您可能知道 高尔夫得分由 18 洞的个人得分组成 我可以想到两种设计模式的方法 创建一个表 每个洞有一列 例如 h1 到 h18 该表具有引用其他表的 FK player id
  • 一种在 C++0x 枚举类中使用所有非限定名称的方法? [复制]

    这个问题在这里已经有答案了 新的 C C 0x 或 C 11 具有一种新类型的枚举 即 枚举类 其中名称的作用域为枚举 除其他外 enum class E VAL1 VAL2 void fun E e E VAL1 Qualified na
  • PHP Imagick - “-量化透明”等效项

    是否有 PHP Imagick 等效项 quantize transparent 量化透明使用示例 http www imagemagick org Usage quantize color trans注意 在页面中搜索 量化透明 Quan
  • 按百分比减少多边形面积

    我有一个由点 x y 组成的多边形 我想做的是将其减少一个百分比 请记住 我不想只是扩大规模 多边形应该有一种内部边界 其宽度取决于百分比 该内部边界被多边形切断 谁知道可以实现这一目标的算法 输入 点数组 百分比 输出 点数组 你所寻求的
  • 当行数 = 0 时删除 Excel 列中的单元格

    我试图删除电子表格中某一列中的所有单元格 0 并 召唤 不在该列顶部的值 我目前正在使用 Dim row index As Integer Dim col index As Integer row index 7 col index 16
  • 如何在 UML 中正式记录 C# 属性?

    在 UML 类图中记录类的 C 属性的正确方法是什么 我还没有决定这是否是我的答案 但我想我会把它扔在那里以便讨论 这看起来可以接受吗 它是属性类型的实例 其中元数据值放入下面的标记值中 我刚刚弄清楚如何添加自定义立体类型 该箭头只是一个标
  • 如何在 scss 中包含仅限 Safari 的样式? [复制]

    这个问题在这里已经有答案了 我只是想修改仅适用于 safari 浏览器的样式属性 这将覆盖默认属性 简单的例子 Default div color blue Safari 浏览器 div color red 我想这可以通过 scss 的 i
  • dotnet 核心并行或同时构建

    In this https github com gatimus DotnetParallelBuild解决方案我有2个应用程序 AppA AppB共享类库Shared 我尝试过自动化这些并行的构建 运行电源外壳 https github
  • 当添加列较少时追加到现有 SQLite 表,而不将数据库读入 R

    是否有一些简单的方法 无论是在 SQL 端还是在 R 端 将 data frame 附加到具有更多列的现有表 缺失的列应该用 NA 填充 如果它能够优雅地处理比表 1 列数更多的表 2 那么会加分吗 library RSQLite Crea
  • Java:如何实现3和?

    我正在研究 3 Sum 来自己实现它 并遇到了以下规则的实现 给定一个由 n 个整数组成的数组 S S 中是否存在满足 a b c 0 的元素 a b c 查找数组中所有总和为零的唯一三元组 注意 三元组 a b c 中的元素必须按非降序排