LeetCode-两数之和

来源：力扣（LeetCode）- 两数之和

问题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解答

初步思路

平时最常用的方法，使用双循环，遍历数组。当内循环的j等于外循环的i时，跳过；当下标为i、j的两数之和等于目标值，则保存i、j，退出循环。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length; j++){
                if(i==j) continue;
                if(nums[i]+nums[j]==target){
                    indexs[0] = i;
                    indexs[1] = j;
                    i = nums.length;
                    break;
                }
            }
        }
        return indexs;
    }
}

缺点：需要循环n*n次，判断n*(n-1)次，耗时，耗内存！

优化

因判定条件是 nums[i] + nums[j] == target ，则 i = 1, j = 2 与 i = 2, j = 1的情况相同。故，初步思路中以 j = 0 为内循环初始条件，甚为不妥！如此，将有大约一半的循环是多余的！同时，要满足 j != i ，则可令 j = i + 1 ，既除去了多余的循环，又满足 j != i 。内循环部分代码如下：

for(int j = 0; j < nums.length; j++){
    if(nums[i]+nums[j]==target){
        indexs[0] = i;
        indexs[1] = j;
        return indexs;
    }
}

虽然减少了进一半的循环，但是，耗时之间少了一点点，所耗内存，依然很大！

借鉴

由 nums[i] + nums[j] = target ，可得两式：

• nums[i] = target - nums[j]

• target - nums[i] = nums[j]

可使用单循环，保存等式左边，寻找等式右边，由此，则将等号单侧的两个变量变为一个，妙哉！

• 保存 target - nums[i] 寻找 nums[j] :

int[] indexs = new int[2];
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.length; i++){
    if(hash.containsKey(nums[i])){
        indexs[0] = hash.get(nums[i]);
        indexs[1] = i;
        break;
    }
    hash.put(target-nums[i],i);
}
return indexs;

• 保存 nums[i] 寻找 target - nums[j] :

int[] indexs = new int[2];
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.length; i++){
    if(hash.containsKey(target - nums[i])){
        indexs[0] = hash.get(nums[i]);
        indexs[1] = i;
        break;
    }
    hash.put(nums[i],i);
}
return indexs;

显然，这次只循环了n次，耗时大幅减少，但是，内存的消耗，似乎并没有减少！