`
yiyidog125
  • 浏览: 13098 次
  • 性别: Icon_minigender_1
  • 来自: 广州
最近访客 更多访客>>
社区版块
存档分类
最新评论

Find all pairs of integers that sum to given value

 
阅读更多
Design an algorithm to find all pairs of integers within an array which sum to a specified
value.

Solution: say the array is X[], given value is M, the solution I know is to create a map containing pairs <M-X[i], count>, when traversing X[], if we find the key exist, that means there is a pair. I think there are two tricky things that people always ignore. One is to handle situation of repeated elements. e.g. {1, 2, 1, 2} and given value is 3. Another is if required to return all these pairs, what data structure will you use ? If you use HashMap, remember all of the keys form a set, you can't store <1, 2> twice.
public class PairSum {

	public static Map<Integer, Integer> getPairSumToN(int[] array, int sum) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		Map<Integer, Integer> result = new IdentityHashMap<Integer, Integer>();
		for (int i : array) {
			if (map.containsKey(i)) {
				result.put(new Integer(i), sum-i);
				int count = map.get(i);
				if (count == 1) {
					map.remove(i);
				} else {
					map.put(i, --count);
				}
			} else {
				if (map.containsKey(sum-i)) {
					int count = map.get(sum-i);
					map.put(sum-i, ++count);
				} else {
					map.put(sum-i, 1);	
				}				
			}
		}
		return result;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = {3, 3, 2, 4, 1, 4, 5, 6, 3, 9, 2, 2};
		System.out.println(getPairSumToN(array, 7));
		System.out.println(getPairSumToN(array, 6));
	}

}

3
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics