两数之和

不积硅步无以至千里

leetcode题库第一题——两数之和
给定一个整数数组和一个整数目标值，返回两个数的下标，这两个数相加和为目标值。
条件1：假定给定的数组中最多有一组数据满足条件。
条件2: 数组中的元素每个只能使用一次。
条件3: 可以以任意顺序返回两个元素的下标。

暂时有两种解决办法：
一、省时间
解决思路： 先从头到尾遍历数组，取到第一个元素之后遍历第一个元素之后的元素，然后判断两数之和是否为target，如果找到了，就保存这两个数的下标，返回结果，如果没有找到，就继续查找下一个元素，再进行判断，如果都遍历完了还没有找到和为target的值，就返回{-1,-1}。
时间复杂度 o(n²)，空间复杂度o(n),

/**
     * @param target   目标和
     * @param orgArray 找查找的数组
     * @return 符合条件的下标
     */

    public int[] searchNum(int target, int[] orgArray) {
        int[] result = {-1, -1};
        for (int i = 0; i < orgArray.length; i++) {
            for (int j = i + 1; j < orgArray.length; j++) {
                if (orgArray[i] + orgArray[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }

二、省空间
解决思路：用一个hashMap来存储整数数组的元素和对应的下标（key存储元素，value存储元素对应的下标），然后遍历数组，判断map中是否存在target - orgArray[i]这样的key，如果存在，就返回map中对应key 的value（对应元素的下标）和i。
如果我自己写，可能会遍历两次，第一次遍历构造map，第二次遍历判断。官方解法中把两次判断和在一起同样可以实现，节省了代码的行数。在以后要写两次遍历的时候，可以考虑一下是不是可以用一次遍历实现。
如果想要节省数组查找的时间，可以考虑用HashMap来实现。
时间复杂度：o(n)
空间复杂度：o(n)

/**
     * 通过hash表来实现
     *
     * @param target
     * @param orgArray
     * @return
     */
    public int[] searchNum2(int target, int[] orgArray) {

        HashMap hashmap = new HashMap<Integer, Integer>();
        for (int i = 0; i < orgArray.length; i++) {
            if (hashmap.containsKey(target - orgArray[i])) {
                return new int[]{(int) hashmap.get(target-orgArray[i]), i};
            }
            hashmap.put(orgArray[i], i);
        }
        return new int[0];
    }