找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1705|回复: 0
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【3Sum】-【刷题第一弹2014】

[复制链接]

14

主题

9

精华

373

积分

高级会员

Rank: 3Rank: 3

积分
373
发表于 10-22-2014 07:33 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:26 AM 编辑

快速通道:
oj.leetcode.com/problems/3sum/

题目:

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

Note:

  • Elements in a triplet (【i】a,【i】b,【i】c) must be in non-descending order. (ie, 【i】a ≤ 【i】b ≤ 【i】c)
  • 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)

建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:
与 Two Sum 类似,固定第一个数,让后面两个数字遍历。
代码:


  1. public class Solution {
  2.     public List<List<Integer>> threeSum(int[] num) {
  3.         List<List<Integer>> ret = new ArrayList<List<Integer>>();
  4.         Arrays.sort(num);
  5.         for(int i=0; i<num.length-2; i++) {
  6.             if(i>0 && num【i】==num[i-1])
  7.                 continue;
  8.             int idx1 = i+1;
  9.             int idx2 = num.length-1;
  10.             while(idx1<idx2) {
  11.                 if (num【i】+num[idx1]+num[idx2]==0) {
  12.                     List<Integer> tmp = new ArrayList<Integer>();
  13.                     tmp.add(num【i】);
  14.                     tmp.add(num[idx1]);
  15.                     tmp.add(num[idx2]);
  16.                     ret.add(tmp);
  17.                     do {idx1++;} while (idx1<idx2 && num[idx1]==num[idx1-1]);
  18.                     do {idx2--;} while (idx1<idx2 && num[idx2]==num[idx2+1]);
  19.                 } else if (num【i】+num[idx1]+num[idx2]<0) {
  20.                     do {idx1++;} while (idx1<idx2 && num[idx1]==num[idx1-1]);
  21.                 } else {
  22.                     do {idx2--;} while (idx1<idx2 && num[idx2]==num[idx2+1]);
  23.                 }
  24.             }
  25.         }
  26.         return ret;
  27.     }
  28. }
复制代码
复杂度:
O(n^2)


本帖被以下淘专辑推荐:

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表