牛客网真题-49-三数之和

固定两个，另一个游标。利用hash查找可能快一些。hash查找的思路是：
先遍历一遍查找，把N-ints[i]作为key，value是arraylist，存放下标，直接使用下标作为value不能解决hash冲突，然后双循环，可以利用排序剪枝当ints[i]+ints[j]>N,就可以终止循环了。判断contains(ints[i]+ints[j]),然后看i,j是否在arraylist里面。

这里是排序二分查找+剪枝。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    public static boolean hasSumEqualN(int[] ints, int N){
        if(ints.length < 3){return false;}
        for(int i = 0; i < ints.length; i++){
            for(int j = i + 1; j < ints.length; j++){
                int l = j + 1, r = ints.length;
                int temp = N - ints[i] - ints[j];
                if(temp > N){
                    return false;
                }
                if(l <= r){
                    if(Arrays.binarySearch(Arrays.copyOfRange(ints, l, r), temp) > 0){
                        return true;
                    }
                }
            }
        }
        return false;
    }


    public static void main(String[] args) throws IOException{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = buf.readLine().split(",");
        int[] ints = Arrays.stream(s[0].split(" ")).parallel().mapToInt(Integer::parseInt).toArray();
        int N = Integer.parseInt(s[1]);
        Arrays.sort(ints);
        if(hasSumEqualN(ints,N)){
            System.out.println("True");
        }else {
            System.out.println("False");
        }
    }
}