当前位置: 首页 > news >正文

[leetcode] 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
  • The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

https://oj.leetcode.com/problems/3sum/

思路1:先排序(用于结果展示和去重),对于每个元素target(注意去重),找另外两个元素使得和为-target,就转化成了n次求2Sum。复杂度O(n^2)。

NSum扩展:可参考 这里

 

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length < 3)
            return result;
        int n = num.length;
        Arrays.sort(num);
        for (int i = 0; i < n; i++) {
            int target = -num[i];
            int p = i + 1, q = n - 1;
            while (p < q) {
                if (num[p] + num[q] < target)
                    p++;
                else if (num[p] + num[q] > target)
                    q--;
                else {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(-target);
                    tmp.add(num[p]);
                    tmp.add(num[q]);
                    result.add(tmp);
                    p++;
                    q--;
                    // remove duplicates
                    while (p < n && num[p] == num[p - 1])
                        p++;
                    while (q >= i + 1 && num[q] == num[q + 1])
                        q--;

                }

            }
            // remove duplicates
            while (i < n - 1 && num[i + 1] == num[i])
                i++;

        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[] { 0 }));
        System.out.println(new Solution().threeSum(new int[] { -1, 0 }));
        System.out.println(new Solution().threeSum(new int[] { 0, 1, -1, }));
        System.out.println(new Solution().threeSum(new int[] { 0, 1, 1, }));

        System.out.println(new Solution().threeSum(new int[] { -1, 0, 1, 2, -1, -4 }));
        System.out.println(new Solution().threeSum(new int[] { 0, 0, 0, 0, 1, -1 }));
        System.out.println(new Solution().threeSum(new int[] { -7, -1, -13, 2, 13, 2, 12, 3, -11, 3, 7, -15, 2, -9,
                -13, -13, 11, -10, 5, -13, 2, -12, 0, -8, 8, -1, 4, 10, -13, -5, -6, -4, 9, -12, 5, 8, 5, 3, -4, 9, 13,
                10, 10, -8, -14, 4, -6, 5, 10, -15, -1, -3, 10, -15, -4, 3, -1, -15, -10, -6, -13, -9, 5, 11, -6, -13,
                -4, 14, -3, 8, 1, -4, -5, -12, 3, -11, 7, 13, 9, 2, 13, -7, 6, 0, -15, -13, -11, -8, 9, -14, 1, 11, -7,
                13, 0, -6, -15, 11, -6, -2, 4, 2, 9, -15, 5, -11, -11, -11, -13, 5, 7, 7, 5, -10, -7, 6, -7, -11, 13,
                9, -10, -9 }));
        System.out.println(new Solution().threeSum(new int[] { -2, 0, 1, 1, 2 }));
        System.out.println(new Solution().threeSum(new int[] { -4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6 }));
    }
}

 

第二遍记录:

  双指针法的运用。

  如何巧妙的去重。

 

参考:

http://tech-wonderland.net/blog/summary-of-ksum-problems.html

http://www.cnblogs.com/TenosDoIt/p/3649607.html

 

 

 

 

转载于:https://www.cnblogs.com/jdflyfly/p/3810688.html

相关文章:

  • 实战CentOS-6.6安装流程
  • idea 使用
  • oracle 数据库相关名词--图解
  • Python服务器开发二:Python网络基础
  • Android Studio 使用本地gradle配置详解
  • CSS规范命名
  • Redis命令详解:Lists
  • 深度学习中的注意力机制
  • PV与并发之间换算的算法 换算公式
  • 序列化组件
  • 日常遇到的问题
  • 添加sudo免密码
  • 利用交通在手数据为换乘添加关注
  • qt注册表关联文件格式
  • [AIR] NativeExtension在IOS下的开发实例 --- IOS项目的创建 (一)
  • Angular2开发踩坑系列-生产环境编译
  • Create React App 使用
  • HTML5新特性总结
  • Javascript基础之Array数组API
  • PHP 程序员也能做的 Java 开发 30分钟使用 netty 轻松打造一个高性能 websocket 服务...
  • redis学习笔记(三):列表、集合、有序集合
  • XML已死 ?
  • 阿里云Kubernetes容器服务上体验Knative
  • 关于springcloud Gateway中的限流
  • 关于字符编码你应该知道的事情
  • 湖南卫视:中国白领因网络偷菜成当代最寂寞的人?
  • 前端攻城师
  • 前端临床手札——文件上传
  • 区块链分支循环
  • 让你成为前端,后端或全栈开发程序员的进阶指南,一门学到老的技术
  • const的用法,特别是用在函数前面与后面的区别
  • $L^p$ 调和函数恒为零
  • (1)(1.13) SiK无线电高级配置(六)
  • (12)Linux 常见的三种进程状态
  • (13)Hive调优——动态分区导致的小文件问题
  • (solr系列:一)使用tomcat部署solr服务
  • (保姆级教程)Mysql中索引、触发器、存储过程、存储函数的概念、作用,以及如何使用索引、存储过程,代码操作演示
  • (简单) HDU 2612 Find a way,BFS。
  • (论文阅读26/100)Weakly-supervised learning with convolutional neural networks
  • (十六)一篇文章学会Java的常用API
  • (转)3D模板阴影原理
  • .Net CF下精确的计时器
  • .NET 反射 Reflect
  • .NET 使用 ILRepack 合并多个程序集(替代 ILMerge),避免引入额外的依赖
  • .Net6使用WebSocket与前端进行通信
  • .net与java建立WebService再互相调用
  • .net专家(张羿专栏)
  • .考试倒计时43天!来提分啦!
  • @Conditional注解详解
  • @TableLogic注解说明,以及对增删改查的影响
  • [ linux ] linux 命令英文全称及解释
  • [8-23]知识梳理:文件系统、Bash基础特性、目录管理、文件管理、文本查看编辑处理...
  • [Android View] 可绘制形状 (Shape Xml)
  • [Angular] 笔记 8:list/detail 页面以及@Input
  • [BT]BUUCTF刷题第8天(3.26)