Determine if an array contains two elements that are equal to a certain amount?

Question

// Checks whether the array contains two elements whose sum is s. // Input: A list of numbers and an integer s // Output: return True if the answer is yes, else return False public static boolean calvalue (int[] numbers, int s){ for (int i=0; i< numbers.length; i++){ for (int j=i+1; j<numbers.length;j++){ if (numbers[i] < s){ if (numbers[i]+numbers[j] == s){ return true; } } } } return false; } 

Answer 1

This can be achieved in O (n).

• Create a hash file from the list so that it contains all the elements of the list. It takes O (n).
• Go through each n element of your list, calculate sn = d and check for the presence of d in the set. If d present, then n+d = s , so return true . If you go through the list without finding a suitable d , return false . This is achieved in a single pass through your list, with each search performed using O (1), so this step also takes O (n).

Answer 2

Both solutions mentioned in other answers to this post, as well as several other answers (for example, using a bitmap instead of a hash table) appear in the following duplicates and small versions of the question:
• Find two elements in the array whose sum is k ,
• Find a pair of elements from the array, the sum of which is equal to a given number ,
• Determine whether or not there are two elements in the set s whose sum is exactly equal,

• Check for the presence of two array numbers up to i ,
• Find a pair of numbers in the array that are added to the given amount ,
• Create an algorithm to find all pairs of integers in an array that are summed with ,
• Given that an unsorted array will find any two elements in the array whose sum is t ,
• A recursive algorithm for finding two integers in an array that is summed with a given inte ,
• Find 2 numbers in an unsorted array equal to a given amount ,
• Find two elements, so the sum is equal to the given value ,
• and, for google, many more .

Answer 3

You can solve this problem by sorting the array, then save 2 pointers at the beginning and end of the array and find 2 numbers by moving both pointers. The sort step takes O (nlog n), and the second step takes O (n).

As @Adam noted, it is also good to remove duplicate elements from the array, so you can shorten the time from the second step if the array contains a lot of duplicate numbers.

How to take the second step:

• Move the pointer back to the end if the sum of the current 2 numbers is greater than n.
• Move the cursor at the beginning forward if the sum of the current 2 numbers is less than n.
• Stop and reject when both pointers point to the same element. Accept if the sum is n.

Why is this correct (I use the right end to indicate the larger end and the left end to indicate the smaller end):

• If the sum is greater than n, it makes no sense to use the right end, since all numbers larger than the current left end will make it worse.
• If the sum is less than n, it makes no sense to use the left end, since all numbers smaller than the current right end will worsen it.
• At each step, we will go through all possible combinations (logically) between the deleted numbers and the remaining numbers. In the end, we will exhaust all possible combinations between all pairs of numbers.

Answer 4

Here is a solution that allows for duplicate entries. It is written in javascript and assumes the array is sorted.

 var count_pairs = function(_arr,x) { if(!x) x = 0; var pairs = 0; var i = 0; var k = _arr.length-1; if((k+1)<2) return pairs; var halfX = x/2; while(i<k) { var curK = _arr[k]; var curI = _arr[i]; var pairsThisLoop = 0; if(curK+curI==x) { // if midpoint and equal find combinations if(curK==curI) { var comb = 1; while(--k>=i) pairs+=(comb++); break; } // count pair and k duplicates pairsThisLoop++; while(_arr[--k]==curK) pairsThisLoop++; // add k side pairs to running total for every i side pair found pairs+=pairsThisLoop; while(_arr[++i]==curI) pairs+=pairsThisLoop; } else { // if we are at a mid point if(curK==curI) break; var distK = Math.abs(halfX-curK); var distI = Math.abs(halfX-curI); if(distI > distK) while(_arr[++i]==curI); else while(_arr[--k]==curK); } } return pairs; } 

Enjoy it!

Answer 5

In java

  private static boolean find(int[] nums, long k, int[] ids) { // walk from both sides towards center. // index[0] keep left side index, index[1] keep right side index, // runtime O(N) int l = ids[0]; int r = ids[1]; if (l == r) { ids[0] = -1; ids[1] = -1; return false; } if (nums[l] + nums[r] == k) { ids[0]++; ids[1]++; return true; } if (nums[l] + nums[r] < k) { ids[0]++; } else { ids[1]--; } return find(nums, k, ids); } public static boolean twoSum(final int[] nums, int target) { // Arrays.sort(nums); //if the nums is not sorted, then sorted it firstly, thus the running time will be O(NlogN) int[] ids = new int[2]; ids[0] = 0; ids[1] = nums.length - 1; return find(nums, target, ids); } 

Test

 @Test(timeout = 10L, expected = Test.None.class) public void test() { Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 6), true); Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 8), false); } 

IF only the answer is not enough and you want to know which one I and j are, that A [i] + A [j] = target

with @cheeken's idea as follows: if there is a duplicate number, take the first that appears first.

  public static int[] twoSum2(final int[] nums, int target) { int[] r = new int[2]; r[0] = -1; r[1] = -1; Set<Integer> set = new HashSet<>(nums.length); Map<Integer, List<Integer>> map = new HashMap<>(nums.length); for (int i = 0; i < nums.length; i++) { int v = nums[i]; if (set.contains(target - v)) { r[0] = map.get(target - v).get(0); r[1] = i; return r; } set.add(v); List ids = map.get(v); if (ids == null) { ids = new LinkedList<>(); ids.add(i); map.put(v, ids); } else { ids.add(i); map.put(v, ids); } } return r; } 

Test

  int[] r = twoSum2(new int[]{3, 2, 4}, 6); Assert.assertEquals(r[0], 1); Assert.assertEquals(r[1], 2); r = twoSum2(new int[]{3, 2, 4}, 8); Assert.assertEquals(r[0], r[1]); Assert.assertEquals(r[1], -1);