确定数组是否包含等于一定和的两个元素？

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

您可以通过排序数组解决这个问题，然后继续2个指针开始和数组的结尾，并通过移动两个指针找到2号。排序步骤采用O（nlog n），第二步采用O（n）。

由于@Adam指出，这也很好地从数组中删除重复的元素，让你可以从第二个步骤的时间缩短，如果数组包含许多重复的号码。

至于如何做第二步：

• 将指针在结束后向如果当前2数之和大于n。
• 如果当前2个数字的和小于n，则将指针移动到开始位置。
• 当两个指针指向相同的元素时停止和拒绝。如果总和等于n，则接受。

为什么这是正确的（我用的右端表示较大端和左端表示小端）：

• 如果总和大于n，则使用权到底有没有点因为所有大于当前左端的数字都会使情况变得更糟。
• 如果sum小于n，则使用左端没有意义，因为小于当前右端的所有数字都会使其变差。
• 在每一步，我们都会经历所有可能的组合（逻辑上）在被移除的数字和剩下的数字之间。最后，我们将耗尽所有数字对之间所有可能的组合。

Answer 2

这可以在O（N）来实现。

1. 从列表中创建一个哈希备份集，使其包含列表的所有元素。这需要O（n）。
2. 通过列表中的每个元素n，计算s-n = d，并检查集合中是否存在d。如果d存在，那么n+d = s，所以返回true。如果您在没有找到合适的d的情况下通过列表，请返回false。这是通过你的列表一次完成的，每次查找都需要O（1），所以这一步也需要O（n）。

Answer 3

无论是在其他的答案中提到这个主题的解决方案，以及一些其他的答案，以及（例如，使用位图，而不是一个哈希表），出现在以下的重复和问题的细微变化：
•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，
•和，每个谷歌，many more。

Answer 4

这里是一个解决方案女巫考虑到重复条目。它是用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; 
} 

享受！

Answer 5

在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(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唯一的答案是不够的，想知道哪一个是i和j的A [1] + A [J] =目标

用@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; 
} 

测试

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