/*给定一个整数数组，以及一个target，查找给定数组内是否存在两个整数的加和是target。找到一次后就终止（假设给定数组里满足条件的只有一对），返回下标。下面是我的做法：
单纯用数组进行遍历，时间复杂度太高。所以想起用map里面的containsValue方法，由于题目假设给定数组满足条件只有一对，所以说明数组内的值是唯一的。将数组的内容作为key，将index作为value。之后可以用key查找到value。
public class TwoSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
TwoSum twoSum=new TwoSum();
int[] test={3,2,4};
int[] result=twoSum.twoSum(test,6);
for (int i : result) {
System.out.print(i+",");
}
}
public int[] twoSum(int[] nums, int target) {
/*Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (map.containsKey(target - x)) {//i=0时，map里面没有内容。i逐渐增加后，每次都只与map中已有的内容（其实就是数组当前内容之前的那些数据）。可以发现这样的做法是可以遍历到所有的可能性的。
return new int[] { map.get(target - x) + 1, i + 1 };
}
map.put(x, i);
}
throw new IllegalArgumentException("No two sum solution");
*/******************此处的方法是手册里的解法，更加简便。在遍历到一个数组内容后，只与其之前的数组内容进行匹配，一边比较一边添加到map中。
Map<Integer, Integer> map=new HashMap<Integer,Integer>();
int[] a=new int[2];
int b;
for(int i=0;i<nums.length;i++){
map.put(nums[i], i+1);
}
for(int i=0;i<nums.length;i++){
b=nums[i];
if(map.containsKey(target-b)&&map.get(target-b)!=i+1){
a[0]=i+1;
a[1]=map.get(target-b);
return a;
}
}
throw new IllegalArgumentException("no solution");
}
}
************************************************************************
如果给定的数组是已经有了排序的，该如何操作？对于已经排序并且实质为查找问题，可以采用二分查找，之前写的二分查找都很复杂，在学习handbook后发现直接下面写法就可以。
public class TwoSumSorted {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums={1,2,3,4,5,6,7};
TwoSumSorted twoSumSorted=new TwoSumSorted();
int[] result=twoSumSorted.twoSum(nums, 3);
for (int i : result) {
System.out.println(i);
}
}
public int[] twoSum(int[] nums,int target) {
int key;
for(int i=0;i<nums.length;i++){
key=target-nums[i];
int j=search(nums,i,key);
if(j!=-1){
return new int[]{i+1,j+1};
}
}
throw new IllegalArgumentException("no such two number");
}
public static int search(int[] nums,int i,int key){
// int a=nums[i];
int start=i+1;
int end=nums.length-1;
while(start<end){
int medium=(start+end)/2;
if(key>nums[medium]){
start=medium+1;//start=medium+1
}else{
end=medium;//end直接等于medium，不用加1
}
}//走到这里说明end<=start,如果数组存在要查找的值，那么在找到这个值后，end会不再更改，start会一直+1到与end相同，这种情况是查找到的结果。
//如果要查找的值不存在，那么会使start>end,或者尽管start==end，nums[start]不等于要找的值。
if(start==end&&nums[start]==key)
return start;
return -1;
}
}
*************************************************************
public int[] twoSum(int[] numbers, int target) {
// Assume input is already sorted.
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
return new int[] { i + 1, j + 1 };
}
}
throw new IllegalArgumentException("No two sum solution");
}
**********************************twoSum3未看，未能理解**************************