本文共 1311 字，大约阅读时间需要 4 分钟。

题目描述

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

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:

题意

给出一个序列，在序列中找三个不同的数a,b,c使a+b+c=0(a,b,c不同是指一个序列只能使用同一位置的数一次),而且要求找出的组合序列唯一，即每一种组合只能出现一次([1,-1,0]与[-1,1,0]就不可以)

思路

我们可以先确定一个数a,去找其他两个数b和c，满足b+c=-a就是我们要找的序列，光光这还不够，我们还要思考找到重复序列的问题。我们可以先把序列排序，然后选择数a的时候与前面的元素比较是否相等，如果相等则选下一个元素，直到与前一个元素不相等为止，这就保证了a不重复。保证了a不重复后，我们要找到合适的b和c，因为序列是有序的，所以我们可以设立left与right指针，分别指向a位置的下一个位置和最右边，通过left和right指针移动来找到合适的b和c，找到一组合适的b和c后，还需要移动left和right指针来找其他满足条件的b和c，这里也有可能找到重复的b和c，所以我们在找下一个b和c的时候一定要与前一个b和c不相同，判定方法与找a的一致。

代码如下

class Solution {
       public List
   
    
     > threeSum(int[] nums) {
           List
     
      
       > list = new ArrayList
       
        
         >(); if(nums.length<=2) return list; Arrays.sort(nums); for (int i=0;i
         
          0) break; //确定a元素不重复 if(i!=0&&nums[i]==nums[i-1]) continue; //目标值为-a int target=-nums[i]; //左右指针 int left=i+1,right=nums.length-1; while(left
          
           left&&nums[right]==nums[right+1]) right--; } //值偏小，left左移 else if(nums[left]+nums[right]
          
         
        
       
      
     
    
   

复杂度

时间复杂度为n*log(n)+n^2

转载地址：http://icaen.baihongyu.com/