题解 | #三数之和#

思路： 这题是两数之和为某个值的改版，首先要理解两数之和为target的解法，然后在此基础上这题就好理解了。

思路1：因为题目要求不能重复，所以可以先对数组排序，然后三指针法暴力遍历数组解决，时间复杂度为O(nlog₂ⁿ)+O(n³)=O(n³)。但思考上面的过程发现排序只是用来去除相同的解，没能利用到升序的特性，所以优化可得到思路2.

思路2：可以想到先遍历数组，同时找基准值，然后每个基准值就相当于target，利用双指针法，一个指向基准值的后一个元素，一个指向数组尾端，二者之和为sum，若sum>target，右指针左移(说明此时和太大，需要减小sum，就需要一个更小的数)，若小于，左指针右移，相等就加入结果List中，这次时间复杂度满足要求。

代码：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //思路2，先排序，然后指定一个基准值作为target，从它的右边利用找两个数和为它
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Arrays.sort(num);
        for(int i=0,len=num.length;i<len-2;i++){
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            findTarget(num,res,-num[i],i);
        }
        return res;
//         //思路1，先排序再三指针暴力法解决，不满足时间复杂度，但可以通过
//         ArrayList<ArrayList<Integer>> res=new ArrayList<>();
//         Arrays.sort(num);
//         int len=num.length;
//         for(int i=0;i<len-2;i++){
//             if(i>0&&num[i]==num[i-1]){
//                 continue;
//             }
//             for(int j=i+1;j<len-1;j++){
//                 if(j>i+1&&num[j]==num[j-1]){
//                     continue;
//                 }
//                 int target=-(num[i]+num[j]);
//                 for(int k=j+1;k<len;k++){
//                     if(k>j+1&&num[k]==num[k-1]){
//                         continue;
//                     }
//                     if(num[k]==target){
//                         ArrayList<Integer> temp=new ArrayList<>();
//                         temp.add(num[i]);
//                         temp.add(num[j]);
//                         temp.add(num[k]);
//                         res.add(temp);
//                     }
//                 }
//             }
//         }
//         return res;
    }
    private void findTarget(int[] num,ArrayList<ArrayList<Integer>> res,int target,int left){
        int i=left+1,j=num.length-1;
        while(i<j){
            int sum=num[i]+num[j];
            if(sum>target){
                j--;
            }else if(sum<target){
                i++;
            }else{
                ArrayList<Integer> temp=new ArrayList<>();
                temp.add(num[left]);
                temp.add(num[i]);
                temp.add(num[j]);
                res.add(temp);
                i++;
                j--;
                while(i<j&&num[i]==num[i-1]){
                    i++;
                }
                while(i<j&&num[j]==num[j+1]){
                    j--;
                }
            }
        }
    }
}