最初のショットでO（nlogn）ソリューションを考える方法は？

Question

私はいつもO(n^2)（ブルートフォース）の解決策を考え出しますが、最初の数分で、あるいは問題を読んだ後に、O(nlogn)またはO(n)には決して行きません。大きなデータセットの場合、O(n^2)は常に失敗します。最適な解決策を得るための問題の考え方へのアプローチ。これについてのいくつかの考えを分かち合うことができますか？ここで私が働いている1つの問題は、大きなデータセット（完全な説明here）のタイムアウトになります。

コード： - 私は

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 
    static int pairs(int[] a,int k) { 

     if(a.length==0 || a==null) 
     return 0; 

     int counter=0;   

     for(int i=0;i<a.length;i++){ 
      for(int j=i+1;j<a.length;j++) { 
       if(Math.abs(a[i]-a[j])==k) 
        counter++; 
      } 
     } 
     return counter; 
    } 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int res; 

     String n = in.nextLine(); 
     String[] n_split = n.split(" "); 

     int _a_size = Integer.parseInt(n_split[0]); 
     int _k = Integer.parseInt(n_split[1]); 

     int[] _a = new int[_a_size]; 
     int _a_item; 
     String next = in.nextLine(); 
     String[] next_split = next.split(" "); 

     for(int _a_i = 0; _a_i < _a_size; _a_i++) { 
      _a_item = Integer.parseInt(next_split[_a_i]); 
      _a[_a_i] = _a_item; 
     } 

     res = pairs(_a,_k); 
     System.out.println(res); 
    } 
} 

Answer 1

ことの一つは、座って、あなたは人間としての問題を解決する方法を探しています。ショートカットやパターンを探します。

この問題では、k個離れた2つの番号を探しています。数字を繰り返します。あなたが行くように、セットにそれらを追加します。その後、プラスまたはマイナスkの数字がセットに含まれている場合は、カウンターを増やします。

擬似コード：

Set<Integer> set; 
for(int i:a){ 
    set.add(i); 
    if(set.contains(i-k) 
    counter++; 
    if(set.contains(i+k) 
    counter++; 
} 
Return counter; 

O（n）の溶液

Answer 2

小さいスカラ溶液vikarjramunが彼の答えのバグを固定していないので：

import scala.collection.mutable._ 

object Solution { 
    def main(args: Array[String]) { 
     val lines = scala.io.Source.stdin.getLines() 
     val k  = lines.next().split(' ')(1).toInt 
     val arr = lines.next().split(' ').map(_.toInt) 

     val set = HashSet[Int]() 
     var count = 0 

     for (i <- arr) { 
      set.add(i); 
      if (set.contains(i - k)) count += 1 
      if (set.contains(i + k)) count += 1 
     } 

     println(count) 
    } 
} 

HashSetが一定の複雑さを有するためルックアップおよび挿入の場合、アルゴリズム全体はO(n)です。