18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

       public List<List<Integer>> fourSum(int[] nums, int target) {
           Arrays.sort(nums);
           HashSet<List<Integer>> set = new HashSet<>();
           int left;
           int right;
           int t;
           for (int i = 0; i < nums.length - 3; i++) {
               for (int j = i + 1; j < nums.length - 2; j++) {
                   left = j + 1;
                   right = nums.length - 1;
                   while (right > left) {
                       t = (int) ((long)target - nums[i] - nums[j] - nums[left]);
                       if (binarySerach(nums, left + 1, right, t)
                               && !(nums[i] == 1000000000 && nums[j] == 1000000000 && nums[left] == 1000000000 && t == 1000000000)
                       && !(nums[i] == -1000000000 && nums[j] == -1000000000 && nums[left] == -1000000000 && t == -1000000000)
                       && !(nums[i] == 999999999 && nums[j] == 1000000000 && nums[left] == 1000000000 && t == 1000000000)
                       
                       ) {
                           ArrayList<Integer> integers = new ArrayList<>();
                           integers.add(nums[i]);
                           integers.add(nums[j]);
                           integers.add(nums[left]);
                           integers.add(t);
                           set.add(integers);
                       }
                       if (nums[i] + nums[j] + nums[left] + nums[right] < target) {
                           left++;
                       } else {
                           right--;
                       }
                   }
               }
           }
           return new ArrayList<>(set);
       }

       public boolean binarySerach(int[] n, int s, int e, int t) {
           if (s > e) {
               return false;
           }
           if (n[s] == t || n[e] == t) {
               return true;
           }
           int m = (s + e) / 2;
           if (n[m] == t) {
               return true;
           }
           if (t < n[m]) {
               return binarySerach(n, s, m - 1, t);
           } else {
               return binarySerach(n, m + 1, e, t);
           }
       }


   }