`
yiyidog125
  • 浏览: 13055 次
  • 性别: 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
分享到:
评论

相关推荐

    c++ abc159f AC 代码

    c++ abc159f AC 代码,适合经常写atcoder的人进行访问。同时,这也有助于你学习c++,你也可以拿此数据进行调试、对拍,找出你的错误。...Find the sum of f(L,R) over all pairs of integers (L,R) such that 1≤L≤R

    算法上机!!

    (1) How many comparisons will Quicksort do on a list of n elements that all have the same value? (2) What are the maximum and minimum number of comparisons will Quicksort do on a list of n elements, ...

    373. Find K Pairs with Smallest Sums查找和最小的k对数字【LeetCode单题讲解系列】

    373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】

    all pairs正交工具

    Allpairs.pl is a Perl script that constructs a reasonably small set of test cases that include all pairings of each value of each of a set of parameters.

    杭州电子科技大学在线oj_1000-1099代码

    《杭州电子科技大学在线oj_1000-1099代码详解》 在编程学习的过程中,参加在线编程竞赛或解决编程题目是提升技能的重要方式。杭州电子科技大学(Hangzhou Dianzi University,简称HDEU)的在线oj平台提供了一系列的...

    leetcode伪代码-number-of-good-pairs:好的对数

    leetcode伪代码numbers-of-good-pairs 题目解读: 题目来源: 原文: Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i &lt; j. Return the number of good pairs. 解读: ...

    java-leetcode题解之Find K Pairs with Smallest Sums.java

    java java_leetcode题解之Find K Pairs with Smallest Sums.java

    findjobj - find java handles of Matlab graphic objects

    Find all java objects contained within a java container or Matlab GUI handle If no output parameter is specified, then an interactive GUI window will be displayed with a tree-view of all container ...

    杭电 ACM 1089

    The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.For each pair of input integers a and b you should output the sum of a and b in one...

    leetcode变形词-Algorithims:我在学习JavaScript的同时解决问题的所有解决方案

    Given an array arr, find element pairs whose sum equal the second argument arg and return the sum of their indices. If multiple pairs are possible that have the same numeric elements but different ...

    Twitterbots: Making Machines that Make Meaning

    which finds and pairs tweets that can be read in iambic pentameter, to the disaster of Microsoft’s @TayAndYou (which “learned” conspiracy theories, racism, and extreme politics from other tweets)....

    杭电题目acm答案

    - **1001 Sum Problem**: Calculate the sum of all numbers up to a given number `n`. This problem demonstrates basic looping and accumulation techniques. - **1089 A+B for Input-Output Practice (I)**: ...

    lodash underscore js库速查手册

    _.findWhere(list, properties) Looks through the list and returns the first value that matches all of the key-value pairs listed in properties. _.reject(list, iterator, [context]) Returns the values in...

    (Unity源码,零积分)非常好点记忆力游戏(找彩蛋)Find The Pairs V.1.0.2 - Admob.zip

    《非常好点记忆力游戏》(Find The Pairs)是一款基于Unity引擎开发的记忆匹配游戏,版本为V.1.0.2,包含Admob广告集成。这款趣味益智游戏旨在锻炼玩家的记忆力和观察能力,通过寻找并配对相同的图片来完成关卡。现在...

    java纸牌程序

    g) a full house (i.e., two cards of one face value and three cards of another face value) [Hint: Add methods getFace and getSuit to class Card of Fig. 7.9.] 4.(7.31Card Shuffling and Dealing) Use the...

    VB.NET多款风格渐变和无规则按钮

    name/value pairs. Each data row contains a name, and value. The row also contains a type or mimetype. Type corresponds to a .NET class that support text/value conversion through the ...

    To-find-the-right-number.rar_number

    Given 2-15 distinct positive integers, and your task is to calculate these numbers there are the number of number of pairs met: the number in a number of other twice.

    ISO15764-2004 Road vehicles extended data link security firstedition

    It is applicable to all data links between pairs of ECUs capable of storing and processing secret data so that unauthorized third parties are denied access to it. Parameters are provided to enable ...

Global site tag (gtag.js) - Google Analytics