分治算法-和为给定数.java

解题思路:
这里有一个精髓是对这个arr数组排序，然后进入递归判断。保证当我们在数组的两端同时向中间遍历时，如果当前两个数的和小于目标值，那么我们需要增加较小的数（也就是左边的数），反之我们需要减小较大的数（也就是右边的数）。如果对数组不进行排序，这个策略就无法保证正确。

注意事项:

对数组进行排序的时候，如果数组中有重复的数字，那么他们的相对位置可能会发生变化。也就是说，如果输入数组中有两个相同的数字，那么排序后他们在数组中的位置可能会发生变化。这可能会影响到最后的结果。例如，如果输入数组是[3, 4, 3, 3]，目标值是7，那么在排序后的数组中，第二个3和第三个3的位置发生了变化，这就导致我们无法找到正确的答案。

这个问题有多种可能的解决方案。例如，我们可以先对数组进行去重处理，然后再进行排序和遍历。或者我们也可以在不排序的情况下遍历数组，然后使用哈希表来存储已经遍历过的数字，以便快速查找是否存在与当前数字的和等于目标值的数字。不同的解决方案有不同的时间和空间复杂度，需要根据具体的问题和数据规模来选择合适的解决方案。

参考代码:

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int[] arr=new int[n];
       for (int i = 0; i < n; i++) {
           arr[i]=sc.nextInt();
       }
       int target=sc.nextInt();
       Arrays.sort(arr);   //排序
       int left=0,right=n-1;
       while(left<right){   //进来left<right,直接避免判断进来递归
           int sum=arr[left]+arr[right];
           if(sum==target){
               System.out.println(arr[left]+" "+arr[right]);
               return;
           }else if (sum<target){
               left++;
           }else {
               right--;
           }
       }
       System.out.println("No");
   }
}