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));
}
}
分享到:
相关推荐
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单题讲解系列】
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代码详解》 在编程学习的过程中,参加在线编程竞赛或解决编程题目是提升技能的重要方式。杭州电子科技大学(Hangzhou Dianzi University,简称HDEU)的在线oj平台提供了一系列的...
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 < j. Return the number of good pairs. 解读: ...
java java_leetcode题解之Find K Pairs with Smallest Sums.java
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 ...
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...
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 ...
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)....
- **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)**: ...
_.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...
《非常好点记忆力游戏》(Find The Pairs)是一款基于Unity引擎开发的记忆匹配游戏,版本为V.1.0.2,包含Admob广告集成。这款趣味益智游戏旨在锻炼玩家的记忆力和观察能力,通过寻找并配对相同的图片来完成关卡。现在...
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...
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 ...
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.
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 ...