2sum问题和3sum问题

╰+攻爆jí腚メ 2022-08-20 09:29 294阅读 0赞

算法 这个书，190页介绍了 这两个问题 。

2sum的意思是 在一组数中，找到 两个数的和为零。有多少个这样的组合。
3sum是 找 有多少三个数的组合 ，他们的和为零。

常规的for循环，问题的规模分别是 平方级别 和立方级别。

使用先排序，然后查找的方式，可以是 对数线性， 和 平方对数级别。
这样就快了一些。

这个转变是 ，把求一个组合的问题 ，转化成 已知一个数，找另一个数的问题。

查找就先排序（归并），再查找，二分。 这样就是 线性对数的速度。

排序的时间是 nlogn, 二分查找的时间是logn ，而者相加是
(n+1)logn 这比 n*n 要曲线更平缓一些。

TwoSumFast

  1. public static int count(int []src){
  2.         //先排序
  3.         Arrays.sort(src);
  4.         int cnt = 0;
  5.         for(int i=0;i<src.length;i++){
  6.             //再用二分查找
  7.             if(BinarySearch.rank(- src[i]) > i)
  8.                 cnt++;
  9.         }
  11.         return cnt;
  12.     }

ThreeSumFast

  1. public static int count(int []src){
  2.         Arrays.sort(src);
  3.         int cnt = 0;
  4.         for(int i=0;i<src.length;i++){
  5.             for(int j=i+1;j<src.length;j++) {
  6.                 if (BinarySearch.rank(-(src[i]+src[j])) > j)
  7.                     cnt++;
  8.             }
  9.         }
  11.         return cnt;
  12.     }

发表评论

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

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

相关阅读

    相关 2sum问题和3sum问题

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

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

    相关 3Sum

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

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