TWO SUM問題まとめ

一、
整数配列を指定し、2つの数値のインデックスを返して、特定のターゲットに集計します.
各入力には1つのソリューションしかありません.同じ要素は2回も使用しません.
例:

  nums = [2,7,11,15]，  = 9，

  nums [ 0 ] + nums [ 1 ] = 2 + 7 = 9，
  [ 0，1 ]。

public int[] twoSum(int[] nums, int target) {
        int[] a=new int[2];
        for(int i=0;i0&&nums[i]==nums[i-1])
        		continue;
        	for(int j=i+1;j

すべての可能な形式を遍歴し,時間複雑度はO(N^2)であった.
ハッシュテーブルを用いて時間を空間的に置き換えることができます

public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
	    Map map = new HashMap();
	    for (int i = 0; i < nums.length; i++) {
	        if (map.containsKey(target - nums[i])) {
	            result[1] = i;
	            result[0] = map.get(target - nums[i]);
	            return result;
	        }
	        map.put(nums[i], i );
	    }
	    return result;
    }

このときの時間的複雑度はO(N)である
二、
昇順で並べ替えられた整数配列を指定し、2つの数値を見つけて、特定のターゲット数に合計します.
関数twoSumは、index 1がindex 2より小さくなければならない2つの数値のインデックスを返します.返される答え(index 1とindex 2)はゼロから始まるものではありません.
各入力には1つのソリューションしかありません.同じ要素は2回も使用しません.
入力:数値={2,7,11,15},ターゲット=9
出力:索引1=1、索引2=2
もちろんハッシュテーブルを用いて,時間的複雑度O(N)のプログラムを実現することができる.しかし、所定の昇順に並べ替えられた整数配列に基づいて、ハッシュテーブルを使用しないで空間を節約する方法を実現することができる.プログラムの流れは:まず、配列の頭の尾のstart、endでそれぞれ1つの数を取って、両者の和を比較して、もし和が大きいならば頭の端を切り取って、startを増加します;和が小さい場合は尾を切り取りendを小さくし,等しくなるまで往復する.

 public int[] twoSum(int[] numbers, int target) {
        int[] a=new int[2];
        int start=0,end=numbers.length-1;
        while(end>start) {
        	int sum=numbers[start]+numbers[end];
        	if(sum>target) {
        		int last=numbers[end];
        		while(end>start&&numbers[--end]==last);
        	}else if(sumstart&&numbers[++start]==first);
        	}else if(sum==target) {
        		a[0]=start+1;
        		a[1]=end+1;
        		return a;
        	}
        }
        return null;
    }

三、
ツリーとターゲット番号が指定され、BSTに2つの要素が存在する場合、それらの和が指定されたターゲットに等しい場合、trueが返されます.
例1:

  ： 
    5
   / \
  3   6
 / \   \
2   4   7

  = 9

  ： 

例2:

  ： 
    5
   / \
  3   6
 / \   \
2   4   7

  = 28

  ：  

プログラムは、シーケンスループ(中シーケンスループ、後シーケンスループ)とハッシュテーブルを組み合わせて実装できます.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean flag=false;
    private Set set=new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
            if(root!=null&&!flag) {
                findTarget(root.left, k);
                findTarget(root.right, k);
                if(set.contains(k-root.val)) {
                    flag=true;
                }
                set.add(root.val);
            }
            return flag;
}
}