首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
华为云
V2EX  ›  算法

20180319-今日算法

  •  
  •   gbin · 154 天前 · 2072 次点击
    这是一个创建于 154 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定一个包含 n 个元素的数组 S,判断 S 中是否存在三个元素 a,b,c 使得 a + b + c = 0 ?找出所有满足条件的组合。

    如 S = [-1, 0, 1, 2, -1, -4] 时, 结果为: [

    [-1, 0, 1],

    [-1, -1, 2]

    ]

    来源 See leetcode

    传送门:https://www.v2ex.com/t/439037

    16 回复  |  直到 2018-03-19 15:16:18 +08:00
        1
    widewing   154 天前 via Android
    排序,然后从零向两边遍历?
        2
    geelaw   154 天前
    一个朴素的方法是先排序,然后枚举前两个元素再二分寻找第三个。
        3
    WordTian   154 天前 via Android
    直接三次循环相加判断,但没上面的方法有效率
        4
    zqqian   154 天前 via Android
    @geelaw 如果 max i 比较小的话,可以放到一个数组里,类似于桶排序。
    可以降低一个 logn 的复杂度
        5
    lhx2008   154 天前 via Android
    做过,标准方法应该是 遍历 2 次,把答案加进 map,变成 2sum 问题,时间复杂度 n^2 空间 n^2,4sum 同理,时间复杂度 n^3
        6
    lhx2008   154 天前 via Android
    @lhx2008 遍历 2 次->两层遍历,两层 for
        7
    gbin   154 天前 via Android
    @geelaw

    数小的时候枚举前两个数只和作为 key 放入 hashmap 中,不用二分法直接 O(1) 查找?
        8
    akio   154 天前
    先转变为 2sum 问题处理就明白了
        9
    gbin   154 天前 via Android
    @lhx2008 和我想的一样。就是不知道是否还有更优的算法?
        10
    zqqian   154 天前 via Android
    先排序
    再枚举一个 n
    然后二分剩下两个数的区间长度
    然后二分两个数的位置
    这样时间复杂度就是 nlognlogn
    @gbin
        11
    Mazexal   154 天前
    预先枚举 c,d 得到 c+d 的 n^2 个数字并排好序。
    双重 for 循环穷举 a,b 的值,再使用二分查找确定 c+d 是否存在。
    c+d 的值得出来后同样枚举得出 c,d 的值。(或者在第一步就浪费一些空间将 c+d 对应的 c,d 存好,此时直接取出即可。)
        12
    victor97   154 天前 via Android
    补充题意:原题要求的是不重复的三元组。
    做法:
    1.先排序,假设 a<=b<=c。
    2.枚举 a 的值,在 a 的后面找 b 和 c
    3.b<=-a/2<=c,以-a/2 为界限,前面入栈,后面出栈,O(n)可以找出所有 bc 组合
    总复杂度应该是 O(n^2),空间复杂度 O(n)
    优化:
    1. 既然不重复,每个数字最多出现两次,多余可以去掉
    2. a<=0, c>=0
        13
    timle1029   154 天前
    最快也就是 O(n^2) 了。Leetcode 上的原题。
    先排序,然后对于每一个元素,从下一个和尾部开始搜索。

    ···java
    public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    if (nums[i] > 0) {
    return res;
    }
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
    int sum = nums[i] + nums[j] + nums[k];
    if (sum == 0) {
    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
    while (j < k && nums[j] == nums[j + 1]) j++;
    while (k > j && nums[k] == nums[k - 1]) k--;
    j++;
    k--;
    } else if (sum > 0) {
    k--;
    } else {
    j++;
    }
    }
    }
    return res;
    }
    ```
        14
    Williamongh   154 天前
    支持楼主,希望能单开一个节点。
        15
    hjdtl   154 天前
    ```javascript

    arr.map((n,i)=>{
    if(i<=arr.length-2){
    for(var s=0;s<arr.length;s++){
    if(s==i||s==i+1) continue;
    if(arr[i]+arr[i+1]==-arr[s]){
    console.log(arr[i],arr[i+1],arr[s]);
    }
    }
    }
    })

    ```

    结果是排列,还要声明一个变量,记录下标,过滤重复的组合。
        16
    yzyun08   154 天前
    资瓷一个
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1151 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 18ms · UTC 17:12 · PVG 01:12 · LAX 10:12 · JFK 13:12
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1