问题描述
n 个整数两两相加可以得到 n(n - 1) / 2 个和。我们的目标是：根据这些和找出原来的 n 个整数。
按非降序排序返回这 n 个数，如果无解，输出 "Impossible"。
测试样例
样例1：
输入：
n = 3, sums = [1269, 1160, 1663]
输出："383 777 886"
样例2：
输入：
n = 3, sums = [1, 1, 1]
输出："Impossible"
样例3：
输入：
n = 5, sums = [226, 223, 225, 224, 227, 229, 228, 226, 225, 227]
输出："111 112 113 114 115"
样例4：
输入：
n = 5, sums = [-1, 0, -1, -2, 1, 0, -1, 1, 0, -1]
输出："-1 -1 0 0 1"
样例5：
输入：
n = 5, sums = [79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932]
输出："39953 39971 39979 39983 39989"
方法一：线性代数矩阵法
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;public class Main {public static String solution(int n, int[] sums) {//判断计算是否正确Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i < sums.length;i++){map.merge(sums[i],1,(oV,nV)->oV+1);}//判断是否可以有整数解int sum = Arrays.stream(sums).sum();//看看所有未知数相加是否是整数if(sum % (n - 1) != 0) return "Impossible";int[] res = null;//排序sums和res，最大和的是最大的两个未知数的和,最小的是最小的两个未知数的和Arrays.sort(sums);//创建矩阵int[][] nums = new int[n][n+1];//解n个未知数的方程最小只需要n个不等式，这时我们已经找到了两个//赋值//赋值从最小的开始赋值，由于以a为基数，所以保证赋值是从小到大的int left = 1;//右指针控制哪个值不需要int right = left + n - 2;int midLeft = right - 1;int midRight = right - 1;while (res == null){//每次操作时进行初始化numsinitNums(nums,n,sums);int index = 1;if(midLeft == midRight){//中间没有一个需要去除的时候for(int i = left;i < right;i++){nums[index++][n] = sums[i];}}else {//中间有需要去除的for(int i = left;i < midLeft;i++){nums[index++][n] = sums[i];}for(int i = midRight;i < right;i++){nums[index++][n] = sums[i];}}//进行计算看看能否解出方程res = JFC(nums);//判断计算是否正确Map<Integer,Integer> temp = new HashMap<>();int resLeft = 0;int resRight = 1;if(res != null){while (resLeft < res.length-1){temp.merge(res[resLeft]+res[resRight],1,(oV,nV)->oV+1);resRight++;if(resRight == res.length){resLeft++;resRight = resLeft + 1;}}for(Map.Entry<Integer,Integer> entry : temp.entrySet()){if(entry.getValue() != map.get(entry.getKey())){res = null;break;}}}right++;midRight++;//该次循环结束if(right == sums.length){midLeft--;midRight = midLeft;right = left + n - 2;}//最头那个元素被排除if(midLeft == left){left++;right = left + n - 2;midLeft = right - 1;midRight = right - 1;}}Arrays.sort(res);StringBuffer sb = new StringBuffer();for(int i = 0;i < res.length;i++){sb.append(res[i]).append(" ");}return sb.substring(0,sb.length()-1);}private static void initNums(int[][] nums, int n, int[] sums) {for(int i = 0;i < n;i++){Arrays.fill(nums[i],0);}//1.最小值nums[0][0] = 1;nums[0][1] = 1;nums[0][n] = sums[0];//2.最大值nums[n-1][n-1] = 1;nums[n-1][n-2] = 1;nums[n-1][n] = sums[sums.length-1];//3.以a为基数，找到剩下n-2个不等式for(int i = 1;i < n-1;i++){nums[i][0] = 1;nums[i][i+1] = 1;}}private static int[] JFC(int[][] nums) {//解方程的函数int length = nums.length;//将矩阵准备好for(int i = 0;i < length;i++){int curr = nums[i][i];for(int j = i + 1;j < length;j++){int temp = nums[j][i];//temp为0时不用整理，直接跳过if(temp != 0) {if(Math.abs(temp) > Math.abs(curr)){//当绝对值temp大于curr时if(Math.abs(temp) % Math.abs(curr) != 0){return null;}else{//计算temp大于curr的倍数int BS = temp / curr;for(int k = 0;k <= length;k++){nums[j][k] -= nums[i][k] * BS;}}}else{//当curr大于temp时int BS;if(temp < 0 && curr < 0){BS = curr / temp;}else{BS = temp / curr;}for(int k = 0;k <= length;k++){if(Math.abs(nums[i][k]) % Math.abs(BS) != 0){return null;}else{nums[j][k] -= nums[i][k] / BS;}}}}}}//开始解开方程int[] res = new int[length];if(Math.abs(nums[length-1][length]) < Math.abs(nums[length-1][length-1]) || Math.abs(nums[length-1][length]) % Math.abs(nums[length-1][length-1]) != 0){return null;}else{res[0] = nums[length-1][length] / nums[length-1][length-1];}for(int i = 1;i < length-1;i++){res[i] = res[i-1] - nums[length - 1 - i][length];}res[length-1] = nums[0][length] - res[length-2];return res;}public static void main(String[] args) {// You can add more test cases hereint[] sums1 = {1269, 1160, 1663};int[] sums2 = {1, 1, 1};int[] sums3 = {226, 223, 225, 224, 227, 229, 228, 226, 225, 227};int[] sums4 = {-1, 0, -1, -2, 1, 0, -1, 1, 0, -1};int[] sums5 = {79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932};System.out.println(solution(3, sums1).equals("383 777 886"));System.out.println(solution(3, sums2).equals("Impossible"));System.out.println(solution(5, sums3).equals("111 112 113 114 115"));System.out.println(solution(5, sums4).equals("-1 -1 0 0 1"));System.out.println(solution(5, sums5).equals("39953 39971 39979 39983 39989"));}
}
