**

• 题目：

**

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例 1：

输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：

• 移出 1 和 4 ，之后 nums = [2,3]
• 移出 2 和 3 ，之后 nums = []
  不再有和为 5 的数对，因此最多执行 2 次操作。
  示例 2：

输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：开始时 nums = [3,1,3,4,3]：

• 移出前两个 3 ，之后nums = [1,4,3]
  不再有和为 6 的数对，因此最多执行 1 次操作。

解法一：哈希表
这个解法是我根据之前做过的两数之和的题解拓展之后写出的，但是放在这道题上，由于其过多的操作导致其时间和空间效率都很低，因此不推荐

class Solution {
   public int maxOperations(int[] nums, int k) {
        int length = nums.length;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        if (length == 0 || length == 1)
            return 0;
        for (int i = 0; i < length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }

            if (map.containsKey(k - nums[i])) {
                int value1 = map.get(k - nums[i]);
                int value2 = map.get(nums[i]);
                if (value1 > 0 && value2 > 0 ){
                    if(k - nums[i] != nums[i]){ //可能会有数字是自身相加等于k，需要另外判断
                        map.put(k - nums[i], map.get(k - nums[i]) - 1);
                        map.put(nums[i], map.get(nums[i]) - 1);
                        ++count;
                    }else if(k - nums[i] == nums[i] && map.get(nums[i]) >= 2){
                        map.put(nums[i], map.get(nums[i]) - 2);
                        ++count;
                    }
                }
            }

        }
        return count;
    }
}

解法二：双指针解法
以nums=[3,2,6,-4,4,18,9,1,14,10,8]，k=10为例，先使用Arrays类的sort方法对数组进行升序排序，则nums=[-4,1,2,3,4,6,8,9,10,14,18]，让i指向第一个元素，即最小的那个数，让j指向最后一个元素，即最大的那个数。然后依次判断nums[i] + nums[j]的情况，直到i和j相遇，有以下3种情况：

• 如果nums[i] + nums[j] == k，则可以对数组执行的最大操作数加1，i指向后一个元素，j指向前一个元素；
• 如果nums[i] + nums[j] > k，那么让j指向前一个元素，i不变。以例子说明，-4+18=14>10，最小的数加上此时j指向的数还比k大，那么此时j指向的那个数就不可能出现在方案里了，因为其他数加上它肯定也会比k大，所以可以不用管那个数了，j--；
• 如果nums[i] + nums[j] < k，同理，可以不用管此时i指向的那个数了，i++

class Solution {
    public int maxOperations(int[] nums, int k) {
        // max 表示可以对数组执行的最大操作数
        int max = 0;
        int len = nums.length;
        // 升序排序
        Arrays.sort(nums);
        int i = 0,j = len - 1;
        while(i < j){
            // 依次处理3种情况
            if(nums[i] + nums[j] == k){
                max++;
                i++;
                j--;
            }else if(nums[i] + nums[j] > k){
                j--;
            }else{
                i++;
            }
        }
        return max;
    }
}