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

题目描述

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。注意：	1.三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）	2.解集中不能包含重复的三元组。

示例

输入：[-2,0,1,1,2]输出：[[-2,0,2],[-2,1,1]]

参考解法

import java.util.ArrayList;import java.util.Arrays;public class Solution {
       public ArrayList
   
    
     > threeSum(int[] num) {
           ArrayList
     
      
       > res = new ArrayList<>();        Arrays.sort(num);        ArrayList
       
         r;        for (int i = 0; i < num.length; i++) {
               // 过滤掉相同的左侧的值            if (i >= 1 && num[i] == num[i - 1])                 continue;            for (int j = i + 1; j < num.length; j++) {
                   // 过滤掉相同的中间的值                if (j >= i + 2 && num[j] == num[j - 1])                     continue;                int rest = -(num[i] + num[j]);                int index = Arrays.binarySearch(num, j + 1, num.length, rest);                // 查找到会返回一个大于等于0的值                if (index >= 0) {
                       r = new ArrayList<>();                    r.add(num[i]);                    r.add(num[j]);                    r.add(num[index]);                    res.add(r);                }            }        }        return res;    }}
       
      
     
    
   

总结

这道题目主要是学习如何处理三个数的关系，用一重循环+双指针代替三重循环。

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