How to write an algorithm to check if the sum of any two numbers in an array/list matches a given number?
How can I write an algorithm to check if the sum of any two numbers in an开发者_运维技巧 array/list matches a given number
with a complexity of nlogn?
I'm sure there's a better way, but here's an idea:
- Sort array
- For every element e in the array, binary search for the complement (sum - e)
Both these operations are O(n log n).
This can be done in O(n) using a hash table. Initialize the table with all numbers in the array, with number as the key, and frequency as the value. Walk through each number in the array, and see if (sum - number) exists in the table. If it does, you have a match. After you've iterated through all numbers in the array, you should have a list of all pairs that sum up to the desired number.
array = initial array
table = hash(array)
S = sum
for each n in array
if table[S-n] exists
print "found numbers" n, S-n
The case where n and table[S-n] refer to the same number twice can be dealt with an extra check, but the complexity remains O(n).
Use a hash table. Insert every number into your hash table, along with its index. Then, let S be your desired sum. For every number array[i] in your initial array, see if S - array[i] exists in your hash table with an index different than i.
Average case is O(n), worst case is O(n^2), so use the binary search solution if you're afraid of the worst case.
Let us say that we want to find two numbers in the array A that when added together equal N.
- Sort the array.
- Find the largest number in the array that is less than N/2. Set the index of that number as lower.
- Initialize upper to be lower + 1.
- Set sum = A[lower] + A[upper].
- If sum == N, done.
- If sum < N, increment upper.
- If sum > N, decrement lower.
- If either lower or upper is outside the array, done without any matches.
- Go back to 4.
The sort can be done in O(n log n). The search is done in linear time.
This is in Java : This even removes the possible duplicates.. Runtime - O(n^2)
private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;
private static void algorithm()
{
Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
for (int i=0; i<intArray.length; i++)
{
intMap.put(i, intArray[i]);
if(intMap.containsValue(sum - intArray[i]))
System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));
}
System.out.println(intMap);
}
def sum_in(numbers, sum_):
"""whether any two numbers from `numbers` form `sum_`."""
a = set(numbers) # O(n)
return any((sum_ - n) in a for n in a) # O(n)
Example:
>>> sum_in([200, -10, -100], 100)
True
Here's a try in C. This isn't marked homework.
// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
int i = 0, k = size - 1;
int curSum;
while(i < k)
{
curSum = array[i] + array[k];
if(curSum == sum)
{
printf("Found match at indices %d, %d\n", i, k);
i++;k--;
}
else if(curSum < sum)
{
i++;
}
else
{
k--;
}
}
}
Here is some test output using int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };
Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..
The search is linear, so O(n). The sort that takes place behind the scenes is going to be O(n*logn) if you use one of the good sorts.
Because of the math behind Big-O, the smaller term in additive terms will effectively drop out of your calculation, and you end up with O(n logn).
This one is O(n)
public static bool doesTargetExistsInList(int Target, int[] inputArray)
{
if (inputArray != null && inputArray.Length > 0 )
{
Hashtable inputHashTable = new Hashtable();
// This hash table will have all the items in the input array and how many times they appeard
Hashtable duplicateItems = new Hashtable();
foreach (int i in inputArray)
{
if (!inputHashTable.ContainsKey(i))
{
inputHashTable.Add(i, Target - i);
duplicateItems.Add(i, 1);
}
else
{
duplicateItems[i] = (int)duplicateItems[i] + 1;
}
}
foreach (DictionaryEntry de in inputHashTable)
{
if ((int)de.Key == (int)de.Value)
{
if ((int)duplicateItems[de.Key] > 1)
return true;
}
else if (inputHashTable.ContainsKey(de.Value))
{
return true;
}
}
}
return false;
}
Here is an algorithm that runs in O(n) if array is already sorted or O(n log n) if it isn't already sorted. Takes cues from lot of other answers here. Code is in Java, but here is a pseudo code as well derived from lot of existing answers, but optimized for duplicates generally
- Lucky guess if first and last elements are equal to target
- Create a Map with current value and its occurrences
- Create a visited Set which contains items we already saw, this optimizes for duplicates such that say with an input of (1,1,1,1,1,1,2) and target 4, we only ever compute for 0 and last element and not all the 1's in the array.
Use these variables to compute existence of target in the array; set the currentValue to array[ith]; set newTarget to target - currentValue; set expectedCount to 2 if currentValue equals newTarget or 1 otherwise
AND return true only if a. we never saw this integer before AND b. we have some value for the newTarget in the map we created c. and the count for the newTarget is equal or greater than the expectedCount
OTHERWISE repeat step 4 till we reach end of array and return false OTHERWISE;
Like I mentioned the best possible use for a visited store is when we have duplicates, it would never help if none of elements are duplicates.
Java Code at https://gist.github.com/eded5dbcee737390acb4
Depends If you want only one sum O(N) or O(N log N) or all sums O(N^2) or O(N^2 log N). In the latter case better uses an FFT>
Step 1 : Sort the array in O(n logn)
Step 2 : Find two indices
0<=i<j<=n in a[0..n] such that a[i]+a[j]==k, where k is given key.
int i=0,j=n;
while(i<j) {
int sum = a[i]+a[j];
if(sum == k)
print(i,j)
else if (sum < k)
i++;
else if (sum > k)
j--;
}
public void sumOfTwoQualToTargetSum()
{
List<int> list= new List<int>();
list.Add(1);
list.Add(3);
list.Add(5);
list.Add(7);
list.Add(9);
int targetsum = 12;
int[] arr = list.ToArray();
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
if ((i != j) && ((arr[i] + arr[j]) == targetsum))
{
Console.Write("i =" + i);
Console.WriteLine("j =" + j);
}
}
}
}
- Solved the question in Swift 4.0
- Solved in 3 different ways (with 2 different type of return -> Boolean and Indexes)
A) TimeComplexity => 0(n Log n) SpaceComplexity => 0(n).
B) TimeComplexity => 0(n^2) SpaceComplexity => 0(1).
C) TimeComplexity => 0(n) SpaceComplexity => 0(n)
Choose Solution A, B or C depending on TradeOff.
//***********************Solution A*********************// //This solution returns TRUE if any such two pairs exist in the array func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //Helper Function if end < start { return -1 } else { let midIndex = (start + end) / 2 if list[midIndex] > key { return binarySearch(list: list, key: key, start: start, end: midIndex - 1) } else if list[midIndex] < key { return binarySearch(list: list, key: key, start: midIndex + 1, end: end) } else { return midIndex } } } func twoPairSum(sum : Int, inputArray: [Int]) -> Bool { //Do this only if array isn't Sorted! let sortedArray = inputArray.sorted() for (currentIndex, value) in sortedArray.enumerated() { if let indexReturned = binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) { if indexReturned != -1 && (indexReturned != currentIndex) { return true } } } return false } //***********************Solution B*********************// //This solution returns the indexes of the two pair elements if any such two pairs exists in the array func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] { for currentIndex in 0..<nums.count { for nextIndex in currentIndex+1..<nums.count { if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) { return [currentIndex, nextIndex] } } } return [] } func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//Helper Function return (firstElement + secondElement) == target } //*******************Solution C*********************// //This solution returns the indexes of the two pair elements if any such two pairs exists in the array func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] { var dict = [Int: Int]() for (index, value) in nums.enumerated() { dict[value] = index } for (index, value) in nums.enumerated() { let otherIndex = dict[(target - value)] if otherIndex != nil && otherIndex != index { return [index, otherIndex!] } } return [] }
This question is missing some more details into it. Like what is the return value, the limitation on the input.
I have seen some questions related to that, which can be this question with extra requirement, to return the actual elements that result in the input
Here is my version of the solution, it should be O(n).
import java.util.*;
public class IntegerSum {
private static final int[] NUMBERS = {1,2,3,4,5,6,7,8,9,10};
public static void main(String[] args) {
int[] result = IntegerSum.isSumExist(7);
System.out.println(Arrays.toString(result));
}
/**
* n = x + y
* 7 = 1 + 6
* 7 - 1 = 6
* 7 - 6 = 1
* The subtraction of one element in the array should result into the value of the other element if it exist;
*/
public static int[] isSumExist(int n) {
// validate the input, based on the question
// This to return the values that actually result in the sum. which is even more tricky
int[] output = new int[2];
Map resultsMap = new HashMap<Integer, Integer>();
// O(n)
for (int number : NUMBERS) {
if ( number > n )
throw new IllegalStateException("The number is not in the array.");
if ( resultsMap.containsKey(number) ) {
output[0] = number;
output[1] = (Integer) resultsMap.get(number);
return output;
}
resultsMap.put(n - number, number);
}
throw new IllegalStateException("The number is not in the array.");
}
}
加载中,请稍侯......
精彩评论