3-sum问题

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

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

  1. import java.util.Arrays;
  3. public class Main { 
  4.     public static void main(String[] args) {
  5.         int[] in = { 3, 4, 5, 6, 1, -6, 8, 21 };
  6.         Arrays.sort(in);
  7.         //-6,1,3,4,5,6,8,21
  8.         Main m = new Main();
  9.         int length = in.length;
  10.         int count = 0;
  11.         for (int i = 0; i < length; i++) {
  12.             for (int j = i + 1; j < length; j++) {
  13.                 // (X > j)的这个动作非常重要，让其向后查找
  14.                 //如果(X != -1)的话，会出现重复的情况，
  15.                 //例如：-6 1 5 和 -6 1 5 重复
  16.                 //会重复查找3两次 ,会出现 -6 3 3 的情况
  17.                 if (m.binarySearch(in, -(in[i] + in[j])) > j) {
  18.                     count++;
  19.                 }
  20.             }
  21.         }
  22.         System.out.println("有"+count+"个3个数和为0的组合");
  23.     }
  24.     //二分查找
  25.     public int binarySearch(int[] in, int key) {
  26.         Arrays.sort(in);
  27.         int lo = 0;
  28.         int hei = in.length - 1;
  29.         while (lo < hei) {
  30.             int mid = hei + (lo - hei) / 2;
  31.             if (key < in[mid]) {
  32.                 hei = mid - 1;
  33.             } else if (key > in[mid]) {
  34.                 lo = mid + 1;
  35.             } else {
  36.                 return mid;
  37.             }
  38.         }
  39.         return -1;
  40.     }
  41. }

发表评论

表情：
评论列表 （有 0 条评论，291人围观）

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

相关阅读

    相关 2sum问题和3sum问题

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

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 297 阅读

    相关 3Sum

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

    水深无声水深无声/ 0 赞/ 272 阅读