Determine if array contains two elements which equal a certain sum?

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).

1. Create a hash-backed set out of your list, such that it contains all elements of the list. This takes O(n).
2. Walk through each element n of your list, calculate s-n = d, and check for the presence of d in the set. If d is present, then n+d = s, so return true. If you pass through the list without finding an appropriate d, return false. This is achieved in a single pass through your list, with each lookup taking O(1), so this step also takes O(n).

Answer 2

Both the solutions mentioned in other answers to this post, and a few other answers as well (eg using a bitmap instead of a hash-table), appear in the following duplicates and slight variations of the question:
• Find two elements in an array that sum to k,
• Find a pair of elements from an array whose sum equals a given number,
• Determine whether or not there exist two elements in set s whose sum is exactly,
• Checking if 2 numbers of array add up to i,
• Find pair of numbers in array that add to given sum,
• Design an algorithm to find all pairs of integers within an array which sum to a,
• Given an unsorted array find any two elements in the array whose sum is equal t,
• A recursive algorithm to find two integers in an array that sums to a given inte,
• Find 2 numbers in an unsorted array equal to a given sum,
• Find two elements so sum is equal to given value,
• and, per google, many more.

Answer 3

You can solve this by sorting the array, then keep 2 pointers to the start and the end of the array and find the 2 numbers by moving both pointers. The sorting step takes O(nlog n) and the 2nd step takes O(n).

As @Adam has pointed out, it is also good to remove duplicate elements from the array, so that you may reduce the time from the second step if the array contains many duplicated numbers.

As for how to do the second step:

• Move the pointer at the end backward if sum of the current 2 numbers is larger than n.
• Move the pointer at the start forward if sum of the current 2 numbers is smaller than n.
• Stop and reject when both pointers point to the same element. Accept if sum is equal to n.

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

• If sum is larger than n, there is no point in using the right end, since all numbers larger than current left end will make it worse.
• If sum is smaller than n, there is no point in using the left end, since all numbers smaller than current right end will make it worse.
• At each step, we will have gone through all possible combinations (logically) between the removed numbers and the numbers which remain. At the end, we will exhaust all possible combinations possible between all pairs of numbers.

Answer 4

Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes 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!

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 answer is not enough, and want to know which one is i and j that the A[i]+A[j]=target

with the idea of @cheeken as following, if there are duplicated number, take the the one appears firstly.

   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);