确定数组中是否包含两个元素，它们是否相等?

// 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;
}

5 个解决方案

#1

This can be achieved in O(n).

这可以在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. 在列表中创建一个hash-back，这样它就包含了列表的所有元素。这需要O(n)。
3. 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).
4. 遍历列表中的每个元素n，计算s-n = d，并检查集合中是否存在d。如果d存在，那么n+d = s，所以返回true。如果你在列表中没有找到合适的d，返回false。这是通过您的列表实现的，每个查找都是O(1)，所以这个步骤也需要O(n)。

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

这篇文章的其他答案中所提到的解决方案，以及其他一些答案(如使用位图代替哈希表)，出现在以下重复和轻微变化的问题中:•找到两个元素的数组和k•找到一双来自一个数组的元素的总和等于一个给定的数字,•确定是否存在两个元素的集合s就是求和,•检查如果2数字数组添加我,•发现一对数字数组添加到给定的总和,•内设计一个算法来找到所有成对的整数数组和一个,•给定一个无序数组找到任何两个元素的数组之和等于t,•一种递归算法，可以在一个数组中找到两个整数，并将其与给定的inte求和，•在一个未排序的数组中找到两个数，等于给定的和，•找到两个元素，这样sum就等于给定的值，•和，每个谷歌，更多。

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

您可以通过对数组进行排序来解决这个问题，然后将两个指针保存到开始和数组的末尾，并通过移动两个指针来查找两个数字。排序步骤为O(nlog n)，第2步为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.

正如@Adam指出的，从数组中删除重复的元素也很好，这样您就可以从第二个步骤中减少时间，如果数组包含许多重复的数字。

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.
• 如果当前两个数字之和大于n，则将指针移到后面。
• Move the pointer at the start forward if sum of the current 2 numbers is smaller than n.
• 如果当前两个数字之和小于n，则在开始时移动指针。
• Stop and reject when both pointers point to the same element. Accept if sum is equal to n.
• 当两个指针指向相同的元素时停止和拒绝。接受如果和等于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.
• 如果sum大于n，那么使用右端是没有意义的，因为所有大于当前左端的数都将使其更糟。
• 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.
• 如果sum小于n，那么使用左端是没有意义的，因为所有小于当前右端的数字都会使它更糟。
• 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.
• 在每一个步骤中，我们将在删除的数字和保留的数字之间进行所有可能的组合(逻辑上)。最后，我们将用尽所有可能的组合在所有对数字之间。

#4

Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes array is sorted.

这里是一个解决方案，女巫考虑了重复的条目。它是用javascript编写的，并假设数组是有序的。

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!

享受吧!

#5

In Java

在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

如果仅仅回答是不够的，并且想知道我和j是哪一个，A[i]+A[j]=目标。

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

有了@cheeken的想法，如果有重复的数字，就先出现一个。

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