LeetCode----数组系列

1877. 数组中最大数对和的最小值

一个数对 (a,b) 的数对和等于 a + b 。最大数对和是一个数对数组中最大的数对和。

比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。
给你一个长度为偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

nums 中每个元素恰好在一个数对中，且
最大数对和的值最小。
请你在最优数对划分的方案下，返回最小的最大数对和
图片说明

解读：首先凑的数对的值要尽量的小，然后在凑成的数对中找最大值

思路一：

先排序然后首尾相加，问题是，怎么证明这个是最优解？

我们以最简单的例子来看，假设有四个数，a >= b >= c >= d，证明最优解为(a, d) 与 (b, c)

证明也很简单，反证法假设最优不是首尾，而是例如(a, c) 和 (b, d) 因为a>=b, c>=d所以最大和为 a + c ，而进一步 a + c >= a + d 且 a + c >= b + c ，因此(a, c)不是最优解，进一步也可以证明(a + b)更不是最优解

以上证明完之后，进一步延伸可知对任意长度数组成立，否则若不是首尾连接则必定能找到当中的四个数abcd对应上面证明的情况

class Solution {
    public int minPairSum(int[] nums) {

        Arrays.sort(nums);  //O(nlogn);
        int res = nums[0] + nums[nums.length-1];
        for(int i=0 ; i < nums.length; i++){
            res = Math.max(res , nums[i] + nums[nums.length-i-1]);
        }
        return res;
    }
}

1743.从相邻元素对还原数组

图片说明

思路:利用哈希表

数组的起点与终点只有一个相邻元素，其余有两个相邻元素（构建HashMap<Integer,List<integer>>）</integer>
遍历数组构建Map<Integer , List<integer>>表（forEach遍历）</integer>
遍历表还原数组，注意判重

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        if(adjacentPairs == null || adjacentPairs.length == 0) return null;
        int[] res = new int[adjacentPairs.length + 1];

        Map<Integer , List<Integer>> map = new HashMap<>();
        for(int[] pair : adjacentPairs){
            map.computeIfAbsent(pair[0] , a -> new ArrayList<Integer>()).add(pair[1]);
            map.computeIfAbsent(pair[1] , a -> new ArrayList<Integer>()).add(pair[0]);
        }

        map.forEach((key , value) -> {
            if(value.size() == 1 && res[0] == res[1]){
                res[0] = key;
                res[1] = value.get(0);
                for(int i = 1 ; i < res.length - 1 ; i++){
                    int nxt = map.get(res[i]).get(0);
                    res[i+1] = nxt == res[i-1] ? map.get(res[i]).get(1) : nxt;
                }
            }
        });
        return res;
    }
}

581.最短无序连续子数组

图片说明

思路：拷贝一个原数组，对其进行排序。对比拷贝数组和原数组，找到原数组两端最大有序片段，中间部分即为最短无序连续子数组

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] numsSorted = new int[nums.length];
        System.arraycopy(nums, 0, numsSorted, 0, nums.length);
        Arrays.sort(numsSorted);

        int left = 0;
        int right = nums.length-1;

        while(nums[left] == numsSorted[left] && left < right){
            left++;
        }
        while(nums[right] == numsSorted[right] && right > 0){
            right--;
        }
        return right == 0 ? 0 : right - left + 1;


    }
}