3-sum问题

快来打我* 2022-06-06 12:16 195阅读 0赞

3-sum问题：统计一个不重复数组中3个数相加为0的组合。

import java.util.Arrays;
    
    public class Main { 
        public static void main(String[] args) {
            int[] in = { 3, 4, 5, 6, 1, -6, 8, 21 };
            Arrays.sort(in);
            //-6,1,3,4,5,6,8,21
            Main m = new Main();
            int length = in.length;
            int count = 0;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    // (X > j)的这个动作非常重要，让其向后查找
                    //如果(X != -1)的话，会出现重复的情况，
                    //例如：-6 1 5 和 -6 1 5 重复
                    //会重复查找3两次 ,会出现 -6 3 3 的情况
                    if (m.binarySearch(in, -(in[i] + in[j])) > j) {
                        count++;
                    }
                }
            }
            System.out.println("有"+count+"个3个数和为0的组合");
        }
        //二分查找
        public int binarySearch(int[] in, int key) {
            Arrays.sort(in);
            int lo = 0;
            int hei = in.length - 1;
            while (lo < hei) {
                int mid = hei + (lo - hei) / 2;
                if (key < in[mid]) {
                    hei = mid - 1;
                } else if (key > in[mid]) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 3 Sum问题

3 Sum 问题题目链接：lintcode 3 sum ([http://www.lintcode.com/en/problem/3sum/][http_www.lin

不念不忘少年蓝@/ 2022年09月25日 00:28/ 0 赞/ 148 阅读

相关 Poj 2549 Sumsets (3Sum问题)

题意：给出一个数集，问其中是否存在a,b,c,d满足a+b+c=d，输出最大的d 理论学习：http://blog.csdn.net/doc\_sgl/article/det

灰太狼/ 2022年08月25日 15:55/ 0 赞/ 177 阅读

相关 2sum问题和3sum问题

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

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

相关 15 3Sum

与之类似的题目有 [1 TwoSum][] [16 3Sum Closest][] [18 4Sum][] import java.util.ArrayL

忘是亡心i/ 2022年08月10日 00:51/ 0 赞/ 163 阅读

相关 3Sum

题目 Given an array S of n integers, are there elements a, b, c in S such that a \+ b \

灰太狼/ 2022年06月07日 13:16/ 0 赞/ 153 阅读

相关 3-sum问题

3-sum问题：统计一个不重复数组中3个数相加为0的组合。 import java.util.Arrays; public class Main {

快来打我*/ 2022年06月06日 12:16/ 0 赞/ 196 阅读

相关 3Sum

[原题链接][Link 1] 给一个拥有n个元素的数组S，S中是否会有a，b，c三个元素使得a+b+c=0?寻找出满足该条件的所有唯一三元组。 Note：答案中必须不

水深无声/ 2022年06月06日 04:43/ 0 赞/ 167 阅读

相关 15. 3Sum

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a +

深藏阁楼爱情的钟/ 2022年04月17日 03:39/ 0 赞/ 234 阅读

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

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

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