Amicable Number Pairs

数A 的所有因数(包括1，不包括A) 之和 等于 B。B的所有因数之和又刚好为A。 且 A != B. 求[1, N] 中所有符合条件的pair

lass Solution {
  public static void main(String[] args) {

    List<List<Integer>> res = Amicable(66992);
    System.out.println(res);
  }
//   1 2 3 4 5 6 7 8 9 
// 1 1 1 1 1 1 1 1 1 1
// 2       2   2   2
// 3           3     3
// 4               

／／sum[i]每个数的因数和
  public static List<List<Integer>> Amicable (int n) {
        // write your code here
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int[] sum= new int[n+1];

        for(int i=0; i<=n; i++){
          sum[i] = 1;
        }
        //最大的因数是n／2， 所以因数的范围是2 ～n/2
        // O(nlogN)  n*(1/2+1/3+1/4....1/n)
         for (int i=2; i<=n/2; i++) {
            for (int j=2*i; j<=n; j+=i)
                sum[j] += i;
        }
      HashMap<Integer,Integer> hash = new HashMap<>();
      for(int i=0; i<=n; i++){
          if(hash.containsKey(i)) {
             if(hash.get(i)==sum[i]){
               List<Integer>list = new ArrayList<>();
               list.add(sum[i]);
               list.add(i);
               res.add(list);
             }
          }
          else{
            hash.put(sum[i],i);
           }
        }

    return res;


    }


}