题解 | #三数之和#TOP54

思路:
1.先排序，不适用暴力破解法
2.使用滑动窗口(两路指针，中间夹)，我们先固定窗口位置 i..j..k,i范围可以从0到n-3，j的范围是i+1到k-1，k的范围是j+1到n-1
3.示例，第一轮遍历，固定i为0，j从i+1= 1开始，k从n-1开始，如果三个数相加大于0,那说明后面两数相加和太大，那就要k--，大数变小点，如果小于0，那说明j的数不够大，j++。
4.注意去重

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        
        if(num == null || num.length < 3){
            return new ArrayList<ArrayList<Integer>>();
        }
        //1.排序
        Arrays.sort(num);
        if(num[0] > 0){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        //1.暴力破解法
//         for(int i = 0;i< num.length - 2;i++){
//             for(int j = i + 1;j<num.length -1;j++){
//                 for(int k = j+ 1; k< num.length;k++){
//                     if(num[i] +num[j] + num[k] == 0){
//                         ArrayList<Integer> ele = new ArrayList<>();
//                         ele.add(num[i]);
//                         ele.add(num[j]);
//                         ele.add(num[k]);
//                         ele.sort((x,y) -> x-y);
//                         if(!result.contains(ele)){
//                             result.add(ele);
//                         }
//                     }
//                 }
//             }
//         }
        //i...j...k
        int n = num.length;
        //2.方法二，两路指针，往中间夹定律。题目中说了不能包含重复的三元组
        for(int i = 0;i< n-2;i++){
            //去重
            if(i > 0 && num[i-1] == num[i]){
                continue;
            }
            int k = n - 1;
            for(int j = i+1; j < k;){
                if(j > i+1 && num[j-1] == num[j]){
                    j++;
                    continue;
                } 
                if(k < n-1 && num[k+1] == num[k]){
                    k --;
                    continue;
                }
                int number = num[i] + num[j] +num[k];
                if(number == 0){
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[k]);
                    result.add(temp);
                    j++;
                    k --;
                }else if(number > 0){
                    k --;
                }else{
                    j ++;
                }
                
            }
            
        }
        
        
        return result;
    }
}