package DataStructure.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和 https://leetcode.cn/problems/4sum/
 * 题目简述:找出一个数组中所有四个不同位置和为target的不重复的四元组
 */
public class FourSum {

 public static void main(String[] args) {
 new FourSum().fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296);
 }

 /**
 * 思路:在三数之和的基础上再套一层指针就行了。需要注意的一个点是,此题设的数据范围为10^9,而int类型的数据范围是[-2^31, 2^31-1],即正负21亿多,故加和可能会出现精度溢出问题,计算加和前需先转为long类型
 */
 public List<List<Integer>> fourSum(int[] nums, int target) {
 List<List<Integer>> result = new ArrayList<>();
 //先排好序
 Arrays.sort(nums);
 //然后从左向右每遍历一个元素a,指针b,c,d使用三数之和的方法扫描[a+1, len-1],寻找所有包含a的四数之和为target的四元组
 for(int a = 0;a < nums.length;a++) {
 //若nums[a]已经大于target并且nums[a] > 0,则后面的元素都已经大于0了,加上去四数之和肯定大于target,直接退出循环
 if(nums[a] > target && nums[a] > 0) break;
 //重复的a元素得出的四元组肯定是一样的,直接过滤掉
 if(a > 0 && nums[a] == nums[a-1]) continue;
 //使用三数之和的方法扫描[a+1, len-1]
 for(int b = a+1;b < nums.length;b++) {
 //若nums[a] + nums[b]已经大于target并且nums[b] > 0,则后面的元素都已经大于0了,加上去四数之和肯定大于target,故退出循环
 if (nums[a] + nums[b] > target && nums[b] > 0) break;
 if(b > a+1 && nums[b] == nums[b-1]) continue;
 int c = b + 1;
 int d = nums.length - 1;
 while(c < d) {
 //只需要将第一个数nums[a]转成long类型就行了
 long sum = (long)nums[a] + nums[b] + nums[c] + nums[d];
 if(sum == target) {
 result.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
 c++;
 while(c < d && nums[c] == nums[c-1]) {
 c++;
 }
 d--;
 while(c < d && nums[d] == nums[d+1]) {
 d--;
 }
 } else if(sum < target) {
 c++;
 } else {
 d--;
 }
 }
 }
 }
 return result;
 }
}