4 
// Checks whether the array contains two elements whose sum is s.
// Input: A list of numbers and an integer s
// Output: return True if the answer is yes, else return False

public static boolean calvalue (int[] numbers, int s){
for (int i=0; i< numbers.length; i++){
    for (int j=i+1; j<numbers.length;j++){
        if (numbers[i] < s){
            if (numbers[i]+numbers[j] == s){
                return true;
                }
            }
        }
    }
    return false;
}
4

5 に答える 5

16

これは O(n) で実現できます。

  1. リストのすべての要素が含まれるように、リストからハッシュに裏打ちされたセットを作成します。これには O(n) かかります。
  2. nリストの各要素をs-n = d調べて、 を計算し、セット内に が存在するかどうかを確認しdます。dが存在する場合はn+d = s、したがって を返しtrueます。適切な が見つからずにリストを通過した場合はd、 を返しfalseます。これは、リストの 1 回のパスで実現され、各ルックアップは O(1) を使用するため、このステップも O(n) を使用します。
于 2012-10-08T03:32:09.120 に答える
7

この投稿の他の回答で言及されている解決策と、他のいくつかの回答（たとえば、ハッシュテーブルの代わりにビットマップを使用する）の両方が、次の重複と質問のわずかなバリエーションに表示されます
。•配列内の2つの要素を検索するその合計はkになり
ます。•合計が指定された数に等しい配列から要素のペアを見つけ
ます。 • 合計が正確にあるセットsに2つの要素が存在するかどうかを判断
します。 • 2つの配列の数が合計してiになるかどうかを確認
します。 •指定された合計に加算される配列内の数値のペアを検索し
ます。• 合計が、になる配列内の整数のすべてのペアを検索するアルゴリズムを設計します。
• ソートされていない配列が与えられた場合、合計がtに等しい配列内の任意の2つの要素を
検索します。 •指定された整数に合計される配列内の2つの整数を検索する再帰アルゴリズム
。 •指定された合計に等しいソートされていない配列内の2つの数値を検索し
ます。 •合計が指定された値に等しくなるように2つの要素を見つけます
。•そして、グーグルごとに、さらに多くの要素を見つけます。

于 2012-10-08T05:31:01.960 に答える
5

これを解決するには、配列を並べ替えてから、配列の先頭と末尾への 2 つのポインターを保持し、両方のポインターを移動して 2 つの数値を見つけます。ソートステップは O(nlog n) かかり、2 番目のステップは O(n) かかります。

@Adam が指摘したように、配列から重複する要素を削除することもお勧めします。これにより、配列に多数の重複した数値が含まれている場合、2 番目のステップからの時間を短縮できます。

2番目のステップを行う方法について：

  • 現在の 2 つの数値の合計が n より大きい場合は、末尾のポインターを後方に移動します。
  • 現在の 2 つの数値の合計が n より小さい場合は、先頭のポインターを前方に移動します。
  • 両方のポインターが同じ要素を指している場合は、停止して拒否します。sum が n に等しい場合に受け入れます。

これが正しい理由は次のとおりです (右端を大きい方の端、左端を小さい方の端として使用します)。

  • sum が n より大きい場合、現在の左端よりも大きいすべての数値が悪化するため、右端を使用しても意味がありません。
  • sum が n より小さい場合、左端を使用しても意味がありません。現在の右端よりも小さいすべての数値がそれを悪化させるからです。
  • 各ステップで、削除された数字と残っている数字の間で (論理的に) 考えられるすべての組み合わせを調べました。最後に、すべての数のペア間で可能なすべての組み合わせを使い果たします。
于 2012-10-08T03:26:24.253 に答える
1

これは、重複エントリを考慮したソリューションです。JavaScript で書かれており、配列がソートされていることを前提としています。

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

楽しみ！

于 2013-03-29T14:20:34.743 に答える
0

Javaで

    private static boolean find(int[] nums, long k, int[] ids) {
    // walk from both sides towards center.
    // index[0] keep left side index, index[1] keep right side index,
    // runtime O(N)
    int l = ids[0];
    int r = ids[1];
    if (l == r) {
        ids[0] = -1;
        ids[1] = -1;
        return false;
    }
    if (nums[l] + nums[r] == k) {
        ids[0]++;
        ids[1]++;
        return true;
    }
    if (nums[l] + nums[r] < k) {
        ids[0]++;
    } else {
        ids[1]--;
    }
    return find(nums, k, ids);
}

public static boolean twoSum(final int[] nums, int target) {
    // Arrays.sort(nums); //if the nums is not sorted, then sorted it firstly, thus the running time will be O(NlogN)
    int[] ids = new int[2];
    ids[0] = 0;
    ids[1] = nums.length - 1;
    return find(nums, target, ids);
}

テスト

@Test(timeout = 10L, expected = Test.None.class)
public void test() {
    Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 6), true);
    Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 8), false);
}

IFだけでは不十分で、A[i]+A[j]=対象のiとjがどちらなのか知りたい

@cheeken の考えでは、次のように、番号が重複している場合は、最初に表示された番号を取ります。

   public static int[] twoSum2(final int[] nums, int target) {
    int[] r = new int[2];
    r[0] = -1;
    r[1] = -1;
    Set<Integer> set = new HashSet<>(nums.length);
    Map<Integer, List<Integer>> map = new HashMap<>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        int v = nums[i];
        if (set.contains(target - v)) {
            r[0] = map.get(target - v).get(0);
            r[1] = i;
            return r;
        }
        set.add(v);
        List ids = map.get(v);
        if (ids == null) {
            ids = new LinkedList<>();
            ids.add(i);
            map.put(v, ids);

        } else {
            ids.add(i);
            map.put(v, ids);
        }
    }
    return r;
}

テスト

    int[] r = twoSum2(new int[]{3, 2, 4}, 6);
    Assert.assertEquals(r[0], 1);
    Assert.assertEquals(r[1], 2);
    r =  twoSum2(new int[]{3, 2, 4}, 8);
    Assert.assertEquals(r[0], r[1]);
    Assert.assertEquals(r[1], -1);
于 2016-02-05T21:03:52.903 に答える