Diffkソリューション

こんにちは、ハッピーコーディング
私はデータ構造とアルゴリズムの概念を改訂する予定です.これは私の最初の試みは、devのブログを書く、はい私は少し神経質です.この動画はお気に入りから削除されています.
今日、私はコーディング問題を解決するつもりですDiffk これは、2つのポインタの概念に基づいています.
フェイスブックインタビュー

Problem Statement - Given an array ‘A’ of sorted integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

時間空間複雑性制約
1 .線形空間の複雑さ以下でこれを試してください.
例

Input :
  A : [1 3 5] 
  k : 4
Output : YES
Explanation : as 5 - 1 = 4

ブルートフォースアプローチ-私たちは2つのインデックスi、jの2つのループを使用し、任意のa [ j ] - a [ i ] = kとi = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =を返します.

int diffPossible(vector<int> &A, int k) {
  int N= A.size();
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (A[j] - A[i] > k) break; // No need check forward because Array is sorted so the difference is going to increase even further because A[I] is going to increase or remain same.
      if (A[j] - A[i] == k) return 1; 
    }
  }
  return 0;
}

このアプローチの時間複雑さはo(n＊n)である.
観察
では、上記のアプローチをチェックしましょうi = I アンドj=J , Diff_1 =(A[J-1]-A[I]) そのようなDiff_1 <k and A[J]-A[I] >k

これはi =I and j> J 我々は解決策を見つけるつもりはないA[j] が増加します(配列がソートされます)A[j]-A[I] .

時i その後増加A[i] それから、増加するでしょうA[J]- A[i] まで減少するj =J-1 我々A[j] -A[i] はDiff_1 これはk (観察1)ので、我々の解決策を見つけることはありませんj =J-1 . 我々が始めないとき、とても効率的なアプローチがありますj 毎回I+1 でもj = jから始めてください.

新しいアプローチコード(時間複雑度:O(n))

int diffPossible(vector<int> &A, int k) {
    int N = A.size();
    int j = 0; 
    for (int i = 0; i < N; i++) {
        j = max(j, i+1);
        while (j < N && (A[j] - A[i] < B)) {
            j += 1;
        }
        if (A[j] - A[i] == B) return 1;
    }
    return 0;
}

Github Solution Link