【两次过】Lintcode 243. 相亲数

两次过】Lintcode 243. 相亲数"/>

【两次过】Lintcode 243. 相亲数

一对整数是相亲数是说他们各自的所有有效因子（除了自己以外的因子）之和等于另外一个数。比如(220, 284)就是一对相亲数。因为：

• 220的所有因子：1+2+4+5+10+11+20+22+44+55+110 = 284
• 284的所有因子：1+2+4+71+142 = 220

给出整数k，求1~k之间的所有相亲数对。

样例

给出 300, 返回 [[220, 284]].

注意事项

对于返回的每对相亲数，要求数对中第一个数小于第二个。

解题思路：

注意两点：

1、求取每个数字的因子时，注意要成对添加，否则会超时。

2、注意需要保持第一个数小于第二个数，筛选掉重复的添加

public class Solution {/** @param k: An integer* @return: all amicable pairs*/public List<List<Integer>> amicablePair(int k) {// write your code hereList<List<Integer>> res = new ArrayList<>();for(int i=220; i < k; i++){int sumi = isum(i);//防止重复添加，eg:220和284, 防止284和220添加if(sumi <= i)continue;if(isum(sumi) == i){List<Integer> list = new ArrayList<>();list.add(i);list.add(sumi);res.add(list);}}return res;}//返回数字i的有效因子的和private int isum(int n){int sum = 1, i;for (i = 2; i * i < n; i++)if (n % i == 0) sum += i + n / i;   //成对相加，eg：2和110, 4和55，5和44...//注意考虑最中间的单数情况if (i * i == n)sum += i;return sum;}
}