从和等于给定数字的数组中找到一对元素

我可以用 O (n)表示。你想知道答案的时候告诉我。注意，它只是简单地遍历数组一次，不进行排序，等等。.我还应该提到，它利用了加法的交换性，不使用散列，而是浪费内存。

使用系统; 使用系统。收集。通用;

/* O (n)方法通过使用查找表存在。方法是将值存储在一个“ bin”中，如果它是一个合适的和的候选值，则可以很容易地查找(例如，O (1))。

例如:

对于数组中的每个 a [ k ] ，我们只需将它放在位置为 x-a [ k ]的另一个数组中。

假设我们有[0,1,5,3,6,9,8,7]和 x = 9

我们创建一个新数组,

指数值

9 - 0 = 9     0
9 - 1 = 8     1
9 - 5 = 4     5
9 - 3 = 6     3
9 - 6 = 3     6
9 - 9 = 0     9
9 - 8 = 1     8
9 - 7 = 2     7

那么唯一重要的值就是那些在新表中有索引的值。

因此，当我们到达9或等于9时，我们看看我们的新数组是否有索引9-9 = 0。因为它是这样的，所以我们知道它包含的所有值都会加到9。(注意，在这个原因，很明显只有一个可能的，但它可能有多个索引值，我们需要存储在其中)。

所以我们最终要做的就是只需要在数组中移动一次。因为加法是可交换的，我们将得到所有可能的结果。

例如，当我们得到6时，我们将索引放入我们的新表9-6 = 3。因为表包含了索引值，所以我们知道这些值。

这实际上是在用速度换取内存。 */

namespace sum
{
class Program
{
static void Main(string[] args)
{
int num = 25;
int X = 10;
var arr = new List<int>();
for(int i = 0; i <= num; i++) arr.Add((new Random((int)(DateTime.Now.Ticks + i*num))).Next(0, num*2));
Console.Write("["); for (int i = 0; i < num - 1; i++) Console.Write(arr[i] + ", "); Console.WriteLine(arr[arr.Count-1] + "] - " + X);
var arrbrute = new List<Tuple<int,int>>();
var arrfast = new List<Tuple<int,int>>();


for(int i = 0; i < num; i++)
for(int j = i+1; j < num; j++)
if (arr[i] + arr[j] == X)
arrbrute.Add(new Tuple<int, int>(arr[i], arr[j]));








int M = 500;
var lookup = new List<List<int>>();
for(int i = 0; i < 1000; i++) lookup.Add(new List<int>());
for(int i = 0; i < num; i++)
{
// Check and see if we have any "matches"
if (lookup[M + X - arr[i]].Count != 0)
{
foreach(var j in lookup[M + X - arr[i]])
arrfast.Add(new Tuple<int, int>(arr[i], arr[j]));
}


lookup[M + arr[i]].Add(i);


}


for(int i = 0; i < arrbrute.Count; i++)
Console.WriteLine(arrbrute[i].Item1 + " + " + arrbrute[i].Item2 + " = " + X);
Console.WriteLine("---------");
for(int i = 0; i < arrfast.Count; i++)
Console.WriteLine(arrfast[i].Item1 + " + " + arrfast[i].Item2 + " = " + X);


Console.ReadKey();
}
}
}

Int [] arr = {1,2,3,4,5,6,7,8,9,0} ;

Var z = (from a in arr 从 b 开始 在哪里10-a = = b 选择 new { a，b })

# Let arr be the given array.
# And K be the give sum




for i=0 to arr.length - 1 do
# key is the element and value is its index.
hash(arr[i]) = i
end-for


for i=0 to arr.length - 1 do
# if K-th element exists and it's different then we found a pair
if hash(K - arr[i]) != i
print "pair i , hash(K - arr[i]) has sum K"
end-if
end-for

Python 实现:

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
if n[0] + n[1] == targetsum:
print str(n[0]) + " + " + str(n[1])

产出:

1 + 4
2 + 3

这将打印这些对，并使用按位操作避免重复。

public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for(int i=0;i<arr.length;i++)
valMap.put(arr[i], i);


int indicesVisited = 0;
for(int i=0;i<arr.length;i++) {
if(valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) {
if(!((indicesVisited & ((1<<i) | (1<<valMap.get(key - arr[i])))) > 0)) {
int diff = key-arr[i];
System.out.println(arr[i] + " " +diff);
indicesVisited = indicesVisited | (1<<i) | (1<<valMap.get(key - arr[i]));
}
}
}
}

我绕过了位操作，只比较了索引值。这个值小于循环迭代值(在本例中为 i)。这也不会打印重复的对和重复的数组元素。

public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
valMap.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
if (valMap.containsKey(key - arr[i])
&& valMap.get(key - arr[i]) != i) {
if (valMap.get(key - arr[i]) < i) {
int diff = key - arr[i];
System.out.println(arr[i] + " " + diff);
}
}
}
}

下面是一个考虑到重复条目的解决方案。它是用 javascript 编写的，并假设数组是排序的。该解决方案在 O (n)时间内运行，除了变量之外不使用任何额外内存。

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

我在一家大公司的面试中解决了这个问题，他们接受了，但我没有。 所以这是给大家的。

从数组的两边开始，慢慢地向内移动，确保在存在重复数据的情况下计数重复数据。

它只计数对，但可以重新工作

• 找到配对
• 查找对 < x
• 查找对 > x

好好享受吧！

C # :

        int[] array = new int[] { 1, 5, 7, 2, 9, 8, 4, 3, 6 }; // given array
int sum = 10; // given sum
for (int i = 0; i <= array.Count() - 1; i++)
if (array.Contains(sum - array[i]))
Console.WriteLine("{0}, {1}", array[i], sum - array[i]);

这是在循环中使用二进制搜索实现的 O (n * lg n)的实现。

#include <iostream>


using namespace std;


bool *inMemory;




int pairSum(int arr[], int n, int k)
{
int count = 0;


if(n==0)
return count;
for (int i = 0; i < n; ++i)
{
int start = 0;
int end = n-1;
while(start <= end)
{
int mid = start + (end-start)/2;
if(i == mid)
break;
else if((arr[i] + arr[mid]) == k && !inMemory[i] && !inMemory[mid])
{
count++;
inMemory[i] = true;
inMemory[mid] = true;
}
else if(arr[i] + arr[mid] >= k)
{
end = mid-1;
}
else
start = mid+1;
}
}
return count;
}




int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
inMemory = new bool[10];
for (int i = 0; i < 10; ++i)
{
inMemory[i] = false;
}
cout << pairSum(arr, 10, 11) << endl;
return 0;
}

在 Java 中的实现: 使用 codives 算法(可能稍有不同)

import java.util.HashMap;


public class ArrayPairSum {




public static void main(String[] args) {


int []a = {2,45,7,3,5,1,8,9};
printSumPairs(a,10);


}




public static void printSumPairs(int []input, int k){
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();


for(int i=0;i<input.length;i++){


if(pairs.containsKey(input[i]))
System.out.println(input[i] +", "+ pairs.get(input[i]));
else
pairs.put(k-input[i], input[i]);
}


}
}

对于 input = {2,45,7,3,5,1,8,9}，如果 Sum 是 10

输出对:

3,7
8,2
9,1

关于解决方案的一些注意事项:

• 我们只在数组中迭代一次—— > O (n)时间
• Hash 中的插入和查找时间为 O (1)。
• 整体时间是 O (n) ，尽管它在散列方面使用了额外的空间。

有三种方法可以解决这个问题:

设和为 T，n 为数组的大小

方法1:
最简单的方法是检查所有的组合(n 选择2)。这个详尽的搜索是 O (n²)。

方法2:
更好的方法是对数组进行排序，这需要 O (n logn)
然后对数组 A 中的每个 x, 使用二进制搜索寻找 T-x。这将采用 O (nlogn)。
所以，整体搜索是 O (n log n)

方法3:
最好的办法 将每个元素插入一个哈希表(不排序)。这需要 O (n)作为常量时间插入。
然后对于每个 x, we can just look up its complement, T-x, which is O(1).
总的来说，这种方法的运行时间是 O (n)。

你可以参考更多的 在这里 。谢谢。

在巨蟒里

arr = [1, 2, 4, 6, 10]
diff_hash = {}
expected_sum = 3
for i in arr:
if diff_hash.has_key(i):
print i, diff_hash[i]
key = expected_sum - i
diff_hash[key] = i

一个解决方案可以是这样的，但不是最优的(这个代码的复杂度是 O (n ^ 2)) :

public class FindPairsEqualToSum {


private static int inputSum = 0;


public static List<String> findPairsForSum(int[] inputArray, int sum) {
List<String> list = new ArrayList<String>();
List<Integer> inputList = new ArrayList<Integer>();
for (int i : inputArray) {
inputList.add(i);
}
for (int i : inputArray) {
int tempInt = sum - i;
if (inputList.contains(tempInt)) {
String pair = String.valueOf(i + ", " + tempInt);
list.add(pair);
}
}
return list;
}
}

一个简单的 python 版本的代码，它可以找到一对零和，并且可以修改为找到 k:

def sumToK(lst):
k = 0  # <- define the k here
d = {} # build a dictionary


# build the hashmap key = val of lst, value = i
for index, val in enumerate(lst):
d[val] = index


# find the key; if a key is in the dict, and not the same index as the current key
for i, val in enumerate(lst):
if (k-val) in d and d[k-val] != i:
return True


return False

函数的运行时复杂度为 O (n) ，空间复杂度为 O (n)。

Java 解决方案。您可以将所有 String 元素添加到字符串的 ArrayList 中并返回该列表。在这里，我只是打印出来。

void numberPairsForSum(int[] array, int sum) {
HashSet<Integer> set = new HashSet<Integer>();
for (int num : array) {
if (set.contains(sum - num)) {
String s = num + ", " + (sum - num) + " add up to " + sum;
System.out.println(s);
}
set.add(num);
}
}

来自 Codeaddict 的不错的解决方案，我自作主张在 Ruby 中实现了一个版本:

def find_sum(arr,sum)
result ={}
h = Hash[arr.map {|i| [i,i]}]
arr.each { |l| result[l] = sum-l  if h[sum-l] && !result[sum-l]  }
result
end

为了允许重复对(1,5) ，(5,1) ，我们只需删除 && !result[sum-l]指令

下面是三种方法的 Java 代码:
1. 使用 MapO (n) ，HashSet 也可以在这里使用。
2. 排序数组，然后使用 BinarySearch 查找补数 O (nLog (n))
3. 传统的 BruteForce 双环 O (n ^ 2)

public class PairsEqualToSum {


public static void main(String[] args) {
int a[] = {1,10,5,8,2,12,6,4};
findPairs1(a,10);
findPairs2(a,10);
findPairs3(a,10);


}




//Method1 - O(N) use a Map to insert values as keys & check for number's complement in map
static void findPairs1(int[]a, int sum){
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
for(int i=0; i<a.length; i++){
if(pairs.containsKey(sum-a[i]))
System.out.println("("+a[i]+","+(sum-a[i])+")");
else
pairs.put(a[i], 0);
}
}






//Method2 - O(nlog(n)) using Sort
static void findPairs2(int[]a, int sum){
Arrays.sort(a);
for(int i=0; i<a.length/2; i++){
int complement = sum - a[i];
int foundAtIndex = Arrays.binarySearch(a,complement);
if(foundAtIndex >0 && foundAtIndex != i) //to avoid situation where binarySearch would find the original and not the complement like "5"
System.out.println("("+a[i]+","+(sum-a[i])+")");
}
}


//Method 3 - Brute Force O(n^2)
static void findPairs3(int[]a, int sum){


for(int i=0; i<a.length; i++){
for(int j=i; j<a.length;j++){
if(a[i]+a[j] == sum)
System.out.println("("+a[i]+","+a[j]+")");
}
}
}


}

一个用 java 编写的简单程序，用于具有唯一元素的数组:

import java.util.*;
public class ArrayPairSum {
public static void main(String[] args) {
int []a = {2,4,7,3,5,1,8,9,5};
sumPairs(a,10);
}


public static void sumPairs(int []input, int k){
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i<input.length;i++){


if(set.contains(input[i]))
System.out.println(input[i] +", "+(k-input[i]));
else
set.add(k-input[i]);
}
}
}

Javascript 解决方案:

var sample_input = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51];
var result = getNumbersOf(100, sample_input, true, []);


function getNumbersOf(targetNum, numbers, unique, res) {
var number = numbers.shift();


if (!numbers.length) {
return res;
}


for (var i = 0; i < numbers.length; i++) {
if ((number + numbers[i]) === targetNum) {
var result = [number, numbers[i]];
if (unique) {
if (JSON.stringify(res).indexOf(JSON.stringify(result)) < 0) {
res.push(result);
}
} else {
res.push(result);
}
numbers.splice(numbers.indexOf(numbers[i]), 1);
break;
}
}
return getNumbersOf(targetNum, numbers, unique, res);
}

O (n)

def find_pairs(L,sum):
s = set(L)
edgeCase = sum/2
if L.count(edgeCase) ==2:
print edgeCase, edgeCase
s.remove(edgeCase)
for i in s:
diff = sum-i
if diff in s:
print i, diff




L = [2,45,7,3,5,1,8,9]
sum = 10
find_pairs(L,sum)

方法: a + b = c，所以我们不寻找(a，b) ，而是寻找 a = c- B

一个简单的 Java 代码片段，用于打印下面的对:

    public static void count_all_pairs_with_given_sum(int arr[], int S){
if(arr.length < 2){
return;
}
HashSet values = new HashSet(arr.length);
for(int value : arr)values.add(value);
for(int value : arr){
int difference = S - value;
if(values.contains(difference) && value<difference){
System.out.printf("(%d, %d) %n", value, difference);
}
}
}

 public static int[] f (final int[] nums, int target) {
int[] r = new int[2];
r[0] = -1;
r[1] = -1;
int[] vIndex = new int[0Xfff];
for (int i = 0; i < nums.length; i++) {
int delta = 0Xff;
int gapIndex = target - nums[i] + delta;
if (vIndex[gapIndex] != 0) {
r[0] = vIndex[gapIndex];
r[1] = i + 1;
return r;
} else {
vIndex[nums[i] + delta] = i + 1;
}
}
return r;
}

C + + 11，运行时复杂度 O (n) :

#include <vector>
#include <unordered_map>
#include <utility>


std::vector<std::pair<int, int>> FindPairsForSum(
const std::vector<int>& data, const int& sum)
{
std::unordered_map<int, size_t> umap;
std::vector<std::pair<int, int>> result;
for (size_t i = 0; i < data.size(); ++i)
{
if (0 < umap.count(sum - data[i]))
{
size_t j = umap[sum - data[i]];
result.push_back({data[i], data[j]});
}
else
{
umap[data[i]] = i;
}
}


return result;
}

Https://github.com/clockzhong/findsumpairnumber

我是在时间和内存空间的 O (m + n)复杂度成本下完成的。 我想这是目前为止最好的算法了。

小于 o (n)的解将等于 >

function(array,k)
var map = {};
for element in array
map(element) = true;
if(map(k-element))
return {k,element}

Swift 中的另一个解决方案是: 创建一个存储(sum-currentValue)值的 hash，并将其与循环的当前值进行比较。复杂度为 O (n)。

func findPair(list: [Int], _ sum: Int) -> [(Int, Int)]? {
var hash = Set<Int>() //save list of value of sum - item.
var dictCount = [Int: Int]() //to avoid the case A*2 = sum where we have only one A in the array
var foundKeys  = Set<Int>() //to avoid duplicated pair in the result.


var result = [(Int, Int)]() //this is for the result.
for item in list {


//keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5)
if (!dictCount.keys.contains(item)) {
dictCount[item] = 1
} else {
dictCount[item] = dictCount[item]! + 1
}


//if my hash does not contain the (sum - item) value -> insert to hash.
if !hash.contains(sum-item) {
hash.insert(sum-item)
}


//check if current item is the same as another hash value or not, if yes, return the tuple.
if hash.contains(item) &&
(dictCount[item] > 1 || sum != item*2) // check if we have item*2 = sum or not.
{
if !foundKeys.contains(item) && !foundKeys.contains(sum-item) {
foundKeys.insert(item) //add to found items in order to not to add duplicated pair.
result.append((item, sum-item))
}
}
}
return result
}


//test:
let a = findPair([2,3,5,4,1,7,6,8,9,5,3,3,3,3,3,3,3,3,3], 14) //will return (8,6) and (9,5)

使用列表内涵的 Python 解决方案

f= [[i,j] for i in list for j in list if j+i==X];

O (N²)

也给出了两个有序对-(a，b)和(b，a)

我的解决方案-Java-没有重复

    public static void printAllPairSum(int[] a, int x){
System.out.printf("printAllPairSum(%s,%d)\n", Arrays.toString(a),x);
if(a==null||a.length==0){
return;
}
int length = a.length;
Map<Integer,Integer> reverseMapOfArray = new HashMap<>(length,1.0f);
for (int i = 0; i < length; i++) {
reverseMapOfArray.put(a[i], i);
}


for (int i = 0; i < length; i++) {
Integer j = reverseMapOfArray.get(x - a[i]);
if(j!=null && i<j){
System.out.printf("a[%d] + a[%d] = %d + %d = %d\n",i,j,a[i],a[j],x);
}
}
System.out.println("------------------------------");
}

刚刚参加了 HackerRank 的这个问题，这是我的 “目标 C”解决方案:

-(NSNumber*)sum:(NSArray*) a andK:(NSNumber*)k {
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
long long count = 0;
for(long i=0;i<a.count;i++){


if(dict[a[i]]) {
count++;
NSLog(@"a[i]: %@, dict[array[i]]: %@", a[i], dict[a[i]]);
}
else{
NSNumber *calcNum = @(k.longLongValue-((NSNumber*)a[i]).longLongValue);
dict[calcNum] = a[i];
}


}
return @(count);
}

希望能帮到别人。

在 Java 中的实现: 使用 cod  演算法:

import java.util.Hashtable;
public class Range {


public static void main(String[] args) {
// TODO Auto-generated method stub
Hashtable mapping = new Hashtable();
int a[]= {80,79,82,81,84,83,85};
int k = 160;


for (int i=0; i < a.length; i++){
mapping.put(a[i], i);
}


for (int i=0; i < a.length; i++){
if (mapping.containsKey(k - a[i]) && (Integer)mapping.get(k-a[i]) != i){
System.out.println(k-a[i]+", "+ a[i]);
}
}


}


}

产出:

81, 79
79, 81

如果你想重复对 (例如: 80,80)也然后只是删除从如果条件的 & & (整数)映射，得到(k-a [ i ]) ! = i，你是好去。

我在没有 Map 的情况下在 Scala 中实现了逻辑。因为计数器循环遍历整个数组元素，所以它会给出重复的对。如果需要重复对，只需返回值 pc

  val arr = Array[Int](8, 7, 2, 5, 3, 1, 5)
val num = 10
var pc = 0
for(i <- arr.indices) {
if(arr.contains(Math.abs(arr(i) - num))) pc += 1
}


println(s"Pairs: ${pc/2}")

它还处理数组中的重复值。

GOLANG 实施情况

func findPairs(slice1 []int, sum int) [][]int {
pairMap := make(map[int]int)
var SliceOfPairs [][]int
for i, v := range slice1 {
if valuei, ok := pairMap[v]; ok {
//fmt.Println("Pair Found", i, valuei)
SliceOfPairs = append(SliceOfPairs, []int{i, valuei})
} else {
pairMap[sum-v] = i
}
}
return SliceOfPairs
}