Если задан список чисел и число k, верните, складываются ли любые два числа из списка до k
Этот вопрос был задан в программном интервью Google. Я думал о двух подходах к тому же:
Найти все подпоследовательности длины. При этом вычислите сумму и двух элементов и проверьте, равно ли она k. Если да, выведите "Да", иначе продолжайте поиск. Это подход грубой силы.
Сортировать массив в порядке убывания. Затем начните обход массива с его правого конца. Скажем, у нас есть отсортированный массив {3,5,7,10}, и мы хотим, чтобы сумма была равна 17. Мы начнем с элемента 10, index=3, давайте обозначим индекс через j. Затем включите текущий элемент и вычислите required_sum= sum - current_element. После этого мы можем выполнить бинарный или тройной поиск в массиве [0- (j-1)], чтобы выяснить, является ли их какой-либо элемент, значение которого равно required_sum. Если мы найдем такой элемент, мы можем сломать, поскольку мы нашли подпоследовательность длины 2, сумма которой равна данной сумме. Если мы не найдем ни одного такого элемента, уменьшите индекс j и повторите вышеупомянутые шаги для получающегося подмассива length= length-1, т.е. исключив элемент с индексом 3 в этом случае.
Здесь мы рассмотрели, что массив может иметь как положительные, так и отрицательные значения.
Можете ли вы предложить лучшее решение, чем это? Решение DP может быть? Решение, которое может еще больше сократить время.
46 ответов
Этот вопрос может быть легко решен с помощью множества в O(N) сложности времени и пространства. Сначала добавьте все элементы массива в набор, а затем просмотрите каждый элемент массива и проверьте, присутствует ли K-ar[i] в множестве. или нет.
Вот код в Java с O(N) сложностью:
boolean flag=false;
HashSet<Long> hashSet = new HashSet<>();
for(int i=0;i<n;i++){
if(hashSet.contains(k-ar[i]))flag=true;
hashSet.add(ar[i]);
}
if(flag)out.println("YES PRESENT");
else out.println("NOT PRESENT");
Вот реализация Java с той же временной сложностью, что и алгоритм, используемый для сортировки массива. Обратите внимание, что это быстрее, чем ваша вторая идея, потому что нам не нужно искать во всем массиве подходящего партнера каждый раз, когда мы проверяем число.
public static boolean containsPairWithSum(int[] a, int x) {
Arrays.sort(a);
for (int i = 0, j = a.length - 1; i < j;) {
int sum = a[i] + a[j];
if (sum < x)
i++;
else if (sum > x)
j--;
else
return true;
}
return false;
}
Это реализация Java с O(n) временной сложностью и O(n) пространством. Идея состоит в том, чтобы иметь HashMap, который будет содержать дополнения каждого элемента массива относительно цели. Если дополнение найдено, у нас есть 2 элемента массива, которые суммируются с целью.
public boolean twoSum(int[] nums, int target) {
if(nums.length == 0 || nums == null) return false;
Map<Integer, Integer> complementMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
if(complementMap.containsKey(target - curr)){
return true;
}
complementMap.put(curr, i);
}
return false;
}
Если вы хотите найти количество пар,
pairs = [3,5,7,10]
k = 17
counter = 0
for i in pairs:
if k - i in pairs:
counter += 1
print(counter//2)
Вот реализация Python
arr=[3,5,7,10]
k=17
flag=False
for i in range(0,len(arr)):
if k-arr[i] in arr:
flag=True
print( flag )
Решение Python:
def FindPairs(arr, k):
for i in range(0, len(arr)):
if k - arr[i] in arr:
return True
return False
A = [1, 4, 45, 6, 10, 8]
n = 100
print(FindPairs(A, n))
Или же
def findpair(list1, k):
for i in range(0, len(list1)):
for j in range(0, len(list1)):
if k == list1[i] + list1[j]:
return True
return False
nums = [10, 5, 6, 7, 3]
k = 100
print(findpair(nums, k))
Решение Javascript:
function hasSumK(arr, k) {
hashMap = {};
for (let value of arr) {
if (hashMap[value]) { return true;} else { hashMap[k - value] = true };
}
return false;
}
Решение может быть найдено только за один проход массива. Инициализируйте хэш-код Set и начните перебирать массив. Если текущий элемент в массиве найден в наборе, тогда вернуть true, иначе добавить дополнение этого элемента (x - arr[i]) к набору. Если итерация массива завершилась без возврата, это означает, что нет такой пары, чья сумма равна x, поэтому верните false.
public boolean containsPairWithSum(int[] a, int x) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i< a.length; i++) {
if(set.contains(a[i]))
return true;
set.add(x - a[i]);
}
return false;
}
C++ решение:
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}
int k;
cin>>k;
int t = false;
for(int i = 0; i < n-1; i++)
{
int s = k-arr[i];
for(int j = i+1; j < n; j++)
{
if(s==arr[j])
t=true;
}
}
if (t){
cout<<"Thank you C++, very cool";
}
else{
cout<<"Damn it!";
}
return 0;
}
Используя Scala, за один проход с O(n) временем и пространственной сложностью.
import collection.mutable.HashMap
def addUpToK(arr: Array[Int], k: Int): Option[Int] = {
val arrayHelper = new HashMap[Int,Int]()
def addUpToKHelper( i: Int): Option[Int] = {
if(i < arr.length){
if(arrayHelper contains k-arr(i) ){
Some(arr(i))
}else{
arrayHelper += (arr(i) -> (k-arr(i)) )
addUpToKHelper( i+1)
}
}else{
None
}
}
addUpToKHelper(0)
}
addUpToK(Array(10, 15, 3, 7), 17)
Код Python:
L = list(map(int,input("Enter List: ").split()))
k = int(input("Enter value: "))
for i in L:
if (k - i) in L:
print("True",k-i,i)
def sum_total(list, total):
dict = {}
for i in lista:
if (total - i) in dict:
return True
else:
dict[i] = i
return False
Вот решение Swift:
func checkTwoSum(array: [Int], k: Int) -> Bool {
var foundPair = false
for n in array {
if array.contains(k - n) {
foundPair = true
break
} else {
foundPair = false
}
}
return foundPair
}
Используя HashSet в java, мы можем сделать это за один раз или с временной сложностью O(n)
import java.util.Arrays;
import java.util.HashSet;
public class One {
public static void main(String[] args) {
sumPairsInOne(10, new Integer[]{8, 4, 3, 7});
}
public static void sumPairsInOne(int sum, Integer[] nums) {
HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(nums));
//adding values to a hash set
for (Integer num : nums) {
if (set.contains(sum - num)) {
System.out.print("Found sum pair => ");
System.out.println(num + " + " + (sum - num) + " = " + sum);
return;
}
}
System.out.println("No matching pairs");
}
}
Реализация Python: код будет выполняться в O(n) сложности с использованием словаря. Мы будем хранить (требуемый_отход - текущий_инвертор) в качестве ключа в словаре. И тогда мы проверим, существует ли число в словаре или нет. Поиск в словаре имеет среднюю сложность как O(1).
def PairToSumK(numList,requiredSum):
dictionary={}
for num in numList:
if requiredSum-num not in dictionary:
dictionary[requiredSum-num]=0
if num in dictionary:
print(num,requiredSum-num)
return True
return False
arr=[10, 5, 3, 7, 3]
print(PairToSumK(arr,6))
Я придумал два решения в C++. Одним из них был наивный тип грубой силы, который был в O(n^2) времени.
int main() {
int N,K;
vector<int> list;
cin >> N >> K;
clock_t tStart = clock();
for(int i = 0;i<N;i++) {
list.push_back(i+1);
}
for(int i = 0;i<N;i++) {
for(int j = 0;j<N;j++) {
if(list[i] + list[j] == K) {
cout << list[i] << " " << list[j] << endl;
cout << "YES" << endl;
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
}
}
cout << "NO" << endl;
printf("Time taken: %f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;}
Как вы можете себе представить, это решение займет много времени при более высоких значениях ввода.
Мое второе решение я смог реализовать за O(N) раз. Использование unordered_set, очень похоже на приведенное выше решение.
#include <iostream>
#include <unordered_set>
#include <time.h>
using namespace std;
int main() {
int N,K;
int trig = 0;
int a,b;
time_t tStart = clock();
unordered_set<int> u;
cin >> N >> K;
for(int i = 1;i<=N;i++) {
if(u.find(abs(K - i)) != u.end()) {
trig = 1;
a = i;
b = abs(K - i);
}
u.insert(i);
}
trig ? cout << "YES" : cout << "NO";
cout << endl;
cout << a << " " << b << endl;
printf("Time taken %fs\n",(double) (clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
Вот Питон. На). Необходимо удалить текущий элемент во время зацикливания, поскольку в списке могут отсутствовать повторяющиеся номера.
def if_sum_is_k(list, k):
i = 0
list_temp = list.copy()
match = False
for e in list:
list_temp.pop(i)
if k - e in list_temp:
match = True
i += 1
list_temp = list.copy()
return match
Javascript
const findPair = (array, k) => {
array.sort((a, b) => a - b);
let left = 0;
let right = array.length - 1;
while (left < right) {
const sum = array[left] + array[right];
if (sum === k) {
return true;
} else if (sum < k) {
left += 1;
} else {
right -= 1;
}
}
return false;
}
Вот реализация C
Для сортировки O (n2) пространственно-временная сложность.
Для решения проблемы Мы используем один проход с O(n) временем и пространственной сложностью через рекурсию.
/ * Учитывая список чисел и число k, возвращаем погоду любые два числа из списка складывают до k. Например, с учетом [10,15,3,7] и k из 17, возврат 10 + 7 равен 17 Бонус: вы можете сделать за один проход? */
#include<stdio.h>
int rec(int i , int j ,int k , int n,int array[])
{
int sum;
for( i = 0 ; i<j ;)
{
sum = array[i] + array[j];
if( sum > k)
{
j--;
}else if( sum < k)
{
i++;
}else if( sum == k )
{
printf("Value equal to sum of array[%d] = %d and array[%d] = %d",i,array[i],j,array[j]);
return 1;//True
}
}
return 0;//False
}
int main()
{
int n ;
printf("Enter The Value of Number of Arrays = ");
scanf("%d",&n);
int array[n],i,j,k,x;
printf("Enter the Number Which you Want to search in addition of Two Number = ");
scanf("%d",&x);
printf("Enter The Value of Array \n");
for( i = 0 ; i <=n-1;i++)
{
printf("Array[%d] = ",i);
scanf("%d",&array[i]);
}
//Sorting of Array
for( i = 0 ; i <=n-1;i++)
{
for( j = 0 ; j <=n-i-1;j++)
{
if( array[j]>array[j+1])
{
//swapping of two using bitwise operator
array[j] = array[j]^array[j+1];
array[j+1] = array[j]^array[j+1];
array[j] = array[j]^array[j+1];
}
}
}
k = x ;
j = n-1;
rec(i,j,k,n,array);
return 0 ;
}
ВЫХОД
Enter The Value of Number of Arrays = 4
Enter the Number Which you Want to search in addition of Two Number = 17
Enter The Value of Array
Array[0] = 10
Array[1] = 15
Array[2] = 3
Array[3] = 7
Value equal to sum of array[1] = 7 and array[2] = 10
Process returned 0 (0x0) execution time : 54.206 s
Press any key to continue.
Вот код в Python 3.7 со сложностью O(N):
def findsome(arr,k):
if len(arr)<2:
return False;
for e in arr:
if k>e and (k-e) in arr:
return True
return False
а также лучший пример кода в Python 3.7 со сложностью O(N^2):
def findsomen2 (arr,k):
if len(arr)>1:
j=0
if arr[j] <k:
while j<len(arr):
i =0
while i < len(arr):
if arr[j]+arr[i]==k:
return True
i +=1
j +=1
return False
Решение Javascript
function matchSum(arr, k){
for( var i=0; i < arr.length; i++ ){
for(var j= i+1; j < arr.length; j++){
if (arr[i] + arr[j] === k){
return true;
}
}
}
return false;
}
Решение в JavaScript
эта функция принимает 2 параметра и проходит по длине списка, а внутри цикла есть еще один цикл, который добавляет одно число к другим числам в списке и проверяет сумму, если она равна k или нет
const list = [10, 15, 3, 7];
const k = 17;
function matchSum(list, k){
for (var i = 0; i < list.length; i++) {
list.forEach(num => {
if (num != list[i]) {
if (list[i] + num == k) {
console.log(`${num} + ${list[i]} = ${k} (true)`);
}
}
})
}
}
matchSum(list, k);
Мой ответ с использованием Set in Swift, чтобы время поиска было O(n)
func twoNumbersEqualToK(array: [Int], k: Int) -> Bool {
let objectSet = Set(array)
for element in objectSet {
let x = k - element
if objectSet.contains(x) {
return true
}
}
return false
}
Ответ Javascript с O(n)
function checkPair(arr, n) {
for (var i in arr) {
if (arr.includes(n - arr[i])) {
return true;
}
}
return false;
}
var a = [4,2,8,7,5,77,6,3,22];
var n = 99;
var m = 100;
console.log(checkPair(a, n));
console.log(checkPair(a, m));Используя библиотеку vavr, это можно сделать довольно кратко:
List<Integer> numbers = List(10, 15, 3, 7);
int k = 17;
boolean twoElementsFromTheListAddUpToK = numbers
.filter(number -> number < k)
.crossProduct()
.map(tuple -> tuple._1 + tuple._2)
.exists(number -> number == k);
Daily Coding Problem выпустила версию проблемы в вашем вопросе...
Учитывая список чисел и число k, верните, суммируются ли любые два числа из списка до k.
Например, для [10, 15, 3, 7] и k из 17 верните true, поскольку 10 + 7 равно 17.
Бонус: вы можете сделать это за один проход?
Вот реализация Ruby, основанная на вашем втором предложении. Я не уверен, можно ли сделать оптимизацию.
Предположение: "список чисел" на самом деле представляет собой набор чисел.
def one_pass_solution
k = 17
arr = [10, 15, 3, 7]
l = 0
r = arr.length-1
arr.sort!
while l < r do
if arr[l] + arr[r] < k
l += 1
elsif arr[l] + arr[r] > k
r -= 1
else
return true
end
end
return false
end
Мой ответ на ежедневную проблему кодирования
# Python 2.7
def pairSumK (arr, goal):
return any(map(lambda x: (goal - x) in arr, arr))
arr = [10, 15, 3, 7]
print pairSumK(arr, 17)
Я пробовал решение в Go Lang. Тем не менее, он потребляет O(n^2) времени.
package main
import "fmt"
func twoNosAddUptoK(arr []int, k int) bool{
// O(N^2)
for i:=0; i<len(arr); i++{
for j:=1; j<len(arr);j++ {
if arr[i]+arr[j] ==k{
return true
}
}
}
return false
}
func main(){
xs := []int{10, 15, 3, 7}
fmt.Println(twoNosAddUptoK(xs, 17))
}
С O(N) сложностью
private static boolean check_add_up(int[] numbers, int total) {
Set<Integer> remainders = new HashSet<>();
int remainder;
for (int number : numbers ) {
if (remainders.contains(number)) {
return true;
}
remainder = total - number;
if(!remainders.contains(remainder)){
remainders.add(remainder);
}
}
return false;
}
В большинстве опубликованных решений не учитывается, что k вдвое больше любого из чисел в списке, тогда их решения будут генерировать ложные срабатывания. Следующий код также учитывает этот случай. Поскольку операций с множеством является O(1), наше окончательное решение является однопроходным решением O(N).
from typing import Optional, List
def add_upto_k(k: int, array: Optional[List] = None) -> bool:
assert array, "Non array input"
assert len(array) != 0, "Array is empty"
diff_set = set()
for iterator in array:
diff = k - iterator
if iterator in diff_set:
return True
diff_set.add(diff)
return False
if __name__ == "__main__":
print(add_upto_k(k=17, array=[10, 15, 3, 7])) # True
print(add_upto_k(k=15, array=[10, 15, 3, 7])) # False
print(add_upto_k(k=20, array=[10, 15, 3, 10])) # True
print(add_upto_k(k=20, array=[10, 15, 3, 7])) # False