Two Sum

题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

题目描述：
给定一个 int 类型的数组，给定一个目标值，返回数组中任意两个值相加和等于目标值的值的下标数组

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目分析

/**
    提示： 
        假设每个输入都最少有一个，并且每个元素不能使用两次
    题解思路：
        题解假设：  
            1. 给定数组是否是排序后的 
            2. 给定的数组中是否有负数
            3. 给定数组中是否有一组以上和为目标值
        思路：
            1. 利用二分查找将数组进行分割，只保留小于目标值的部分 
            2. 初始化双层数组
            3. 利用双层循环进行遍历剩余数组元素，将其对应的 i j 保存到一个数组中
 */

题解

/**
    varsion 1
 */

class Solution_v1 {
/**
    获取符合目标的数组,
    通过递归的方式获取符合目标的数组
 */
public int[] targetArray(int[] nums, int target){
    if(nums.count <= 0) return nums;
    int index = nums.count / 2;
    if(nums[index] < target) {
        return nums.suArray(0, index);
    }else {
        subArray(nums.subArray(0, index), target);
    }
}

/**
    根据优化后的值，
    sums.count = 4
    i = 0, j = 0; 0 + 0, 0 + 1, 0 + 2, 0 + 3
    i = 1, j = 1; 1 + 1, 1 + 2, 1 + 3 
    i = 2, j = 2; 2 + 2, 2 + 3 
    i = 3, j = 3; 3 + 3
 */
public int[] twoSum(int[] sums, int target){
    int [][] result;
    for(int i = 0; i < sums.count; i++){
        for(int j = i ; i < sums.count; j++ ){
            if(sums[i ] + sums[j] == target){
                result.addObject([i, j]);
            }
        }
    }
}
}

/**
    说明： 
        通过以上方式，虽然通过递归的二分方法将原始数据进行了缩减  
        但是其根本的方式还是利用了双层for 循环嵌套的方式实现，其时间复杂度
        还是 O(n*n) 的 ，只不过通过方法1 缩减了n 的等量级
 */


/**------------------------------------------------------- */
/** 
    version 2

    反复理解题目， 需要找到的是 数组中 a + b = target   ，可以将其简单理解为 
    一种 a  b  配对， 配对条件为  a + b = target, 针对配对操作，KV 是非常合适的
    K 为 要查找的B 值 ， value 是需要 A 值索引 


    思路： 
        通过 map 集合的方式，以 value 为key, index 为值存储 
        通过循环数组，然后遍 历其中每个值 
        如果 target - array[index] contain map 中，那么久返回对应的值，
        如果没在那么久直接将 array[index] 放入map 中
 */

class  Solution_v2 {
    public  int[] twoSum (int[] numbers , int target ){
        // 结果的 数组  
        int [] result = new int[2];
        // 创建map 结构
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 遍历目标数组
        for(int i = 0; i < numbers.length; i++){
            // 判断map 中是否包含与之对应的key  
            if(map.containKey(target - numbers[i])){
                result[1] = i+1;
                result[0] = map.get(target - number[i]);
                // 删除其已有的元素，
                return result;
            }
            map.put(number[i], i + 1);
        }
        return result;
    }
}

/**
    算法总结： 
        方法2 虽然解决了问题，但是其并没有解决每个元素只使用一次的问题


 */



/** 
 * 
 * 算法测试
 * 
 */

 class Test {
    public static void main(String[] args) {
        System.out.println("测试");
    }

}