2-sum问题的线性对数级别的解法

深碍√TFBOYSˉ_ 2021-07-24 16:23 300阅读 0赞

# 一 代码 #

package common;
    
    import BinarySearch.BinarySearch;
    
    import java.util.Arrays;
    
    /**
    * @ClassName: TwoSumFast
    * @Description: 2-sum问题的线性对数级别的解法
    * @Date: 2021/2/22
    * @Author: cakin
    */
    public class TwoSumFast {
        /**
         * 功能描述：计算和为0的整数对的数目
         *
         * @param a 数组
         * @return 和为0的个数
         * @author cakin
         * @date 2021/2/22
         */
        public static int count(int[] a) {
            Arrays.sort(a);
            int N = a.length;
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                if (BinarySearch.indexOf(a, -a[i]) > i) {
                    cnt++;
                }
            }
            return cnt;
        }
    
        public static void main(String[] args) {
            In in = new In(args[0]);
            int[] a = in.readAllInts();
    
            Stopwatch timer = new Stopwatch();
            int count = count(a);
            StdOut.println("elapsed time = " + timer.elapsedTime());
            StdOut.println(count);
        }
    }

# 二 测试 #

F:\Algorithm\target\classes>java common.TwoSumFast 1Mints.txt
    elapsed time = 0.189
    249838

# 三 测试说明 #

该算法是线性对数级别的。

发表评论取消回复

表情：

评论列表（有 0 条评论，300人围观）

还没有评论，来说两句吧...

相关阅读

相关 TopK问题的必会解法

目录经典解法，创建K个大小的堆不考虑空间的暴力排序做法不考虑空间的快排partition变形减治法思想(核心：找第K大的数)

╰半夏微凉°/ 2024年03月30日 13:36/ 0 赞/ 57 阅读

相关 2.2线性表-线性表的类型定义

对线性表的数据元素不仅可以进行各种访问，还可以进行插入和删除操作。 ADT List\{ 　　数据对象　　数据关系　　数据操作 \} 转载于:https://

妖狐艹你老母/ 2023年08月17日 16:14/ 0 赞/ 102 阅读

相关凎！一个函数秒杀 2Sum 3Sum 4Sum 问题

点击上方“五分钟学算法”，选择“星标”公众号重磅干货，第一时间送达![format_png][] ![format_png 1][]来源：labuladong 经常刷

r囧r小猫/ 2023年02月25日 07:20/ 0 赞/ 44 阅读

相关 2sum问题和3sum问题

算法这个书，190页介绍了这两个问题。 2sum的意思是在一组数中，找到两个数的和为零。有多少个这样的组合。 3sum是找有多少三个数的组合，他们的和为零

╰+攻爆jí腚メ/ 2022年08月20日 09:29/ 0 赞/ 172 阅读

相关【LeetCode】39. Combination Sum & 40. Combination Sum II分析及解法&DFS

39. Combination Sum Total Accepted: 87334 Total Submissions: 283947 Difficulty: Medium

一时失言乱红尘/ 2022年07月25日 15:39/ 0 赞/ 149 阅读

相关 leetcode 15. 3Sum 以及2Sum的问题的处理和求解

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?

我会带着你远行/ 2022年06月09日 06:57/ 0 赞/ 163 阅读

相关 8皇后问题的解法

传统办法-回溯法 include<iostream> include<math.h> using namespace std;

冷不防/ 2022年05月09日 17:52/ 0 赞/ 149 阅读

相关 [python解法] LEETCODE 算法题一：two sum

题干： Given an array of integers, return indices of the two numbers such that they add up

叁歲伎倆/ 2022年04月16日 05:23/ 0 赞/ 124 阅读

相关 3-sum问题平方对数级别算法

一代码 / Compilation: javac ThreeSumFast.java Execution: java Thr

港控/mmm°/ 2021年07月24日 19:58/ 0 赞/ 415 阅读

相关 2-sum问题的线性对数级别的解法

一代码 package common; import BinarySearch.BinarySearch; import j

深碍√TFBOYSˉ_/ 2021年07月24日 16:23/ 0 赞/ 301 阅读