首页 > 代码库 > 3Sum

3Sum

2024-08-06 11:03:33   216人阅读

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, a ≤ b ≤ 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)
最开始想着直接用穷举法，三重循环，时间复杂度O(N^3)略高，TLE超时，提示说用双指针，百度之，看到http://blog.csdn.net/xiaobaohe/article/details/7857461
用的是穷举法，不过优化了一下，先讲数组排序，然后去重，效率高了一点，600ms左右，java做的
后面百度看双指针如何求解
 1 package com.gxf.test; 2  3  4 import java.util.ArrayList; 5 import java.util.Arrays; 6 import java.util.HashMap; 7  8 import java.util.List; 9 10 11 //class ListNode {12 //      public int val;13 //      public ListNode next;14 //      ListNode(int x) {15 //          val = x;16 //          next = null;17 //      }18 //  }19 20 public class Solution {21     public List<List<Integer>> threeSum(int[] num) {22         List<List<Integer>> result = new ArrayList<List<Integer>>();23         HashMap<String, Integer> map = new HashMap<String, Integer>();24         Arrays.sort(num);25 //        for(int i = 0; i < num.length; i++){26 //            System.out.print(num[i] + " ");27 //        }28 //        System.out.println();29         30         for(int i = 0; i < num.length - 2; i++){31             if(num[i] > 0)32                 break;33             if(i > 0 && num[i] == num[i - 1])34                 continue;                                    //去重35             for(int j = i + 1; j < num.length - 1; j++){36                 if(j > i + 1 && num[j] == num[j - 1])37                     continue;                                //去重38                 for(int k = j + 1; k < num.length; k++){39                     if(k > j + 1 && num[k] == num[k - 1])40                         continue;                            //去重41                     if(num[i] + num[j] + num[k] == 0){42                         List<Integer> element = new ArrayList<Integer>();43                         44                         element.add(num[i]);45                         element.add(num[j]);46                         element.add(num[k]);47                         48                         result.add(element);49                     }50                 }51             }52         }53         54                55         return result;56     }57 }

 下面是用双指针做的，时间复杂度好像为O(n*logn)

 1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.HashMap; 4  5 import java.util.List; 6  7  8 //class ListNode { 9 //      public int val;10 //      public ListNode next;11 //      ListNode(int x) {12 //          val = x;13 //          next = null;14 //      }15 //  }16 17 public class Solution {18     public List<List<Integer>> threeSum(int[] num) {19         List<List<Integer>> result = new ArrayList<List<Integer>>();20         Arrays.sort(num);                            //将数组升序排序21         22         for(int i = 0; i < num.length; i++){23             if(i > 0 && num[i] == num[i - 1])24                 continue;                            //去重25             int j = i + 1;26             int k = num.length - 1;27             while(j < k){                            //从i + 1 ~ n - 1中找出两个数等于-num[i]28                 if(j > i + 1 && num[j] == num[j - 1])29                 {30                     j++;31                     continue;32                 }33                 if(k < num.length - 1 && num[k] == num[k + 1]){34                     k--;35                     continue;36                 }                                    //去重37                 int temp = num[i] + num[j] + num[k];38                 if(temp > 0){                        //结果比0大k前移39                     k--;40                     continue;41                 }42                 else if(temp < 0){43                     j++;44                     continue;45                 }else{                                //找到一个解46                     List<Integer> element = new ArrayList<Integer>();47                     element.add(num[i]);48                     element.add(num[j]);49                     element.add(num[k]);50                     result.add(element);51                     j++;52                     //break;                            //退出循环53                 }54                 55             }56         }57                58         return result;59     }60 }

参考：http://www.cnblogs.com/lihaozy/archive/2013/01/23/2872427.html

3Sum


联系
我们