1. ホーム
  2. algorithm

[解決済み] 配列から、和が指定された数に等しい要素の組を求めよ。

2022-06-20 18:57:06

質問

n個の整数の配列が与えられ、数Xが与えられたとき、その和がXに等しいユニークな要素の組(a,b)を全て求めよ。

以下は私の解答ですが、O(nLog(n)+n)となりますが、最適かどうかはわかりません。

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr+len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

どのように解決するのですか?

# 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