算法,两数之和

问题来源:two sum

问题描述

给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。 您可以假设每个输入都只有一个解决方案， 而您可能不会使用相同的元素两次。

Example:

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

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

解

正向思维解法

直接遍历所有的组合，求出问题的解

public int[] twoSum(int[] nums, int target) {
     for (int i = 0; i < nums.length; i++) {
           for (int j = i + 1; j < nums.length; j++) {
                    if (target == nums[j] + nums[i]) {
                        return new int[] { i, j };
                    }
         }
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析:
这是最简单的解法。两个嵌套循环，时间复杂度为O(n^{2)。空间复杂度为O(1)}

逆向思维解法

用目标减去加数1，得到加数2，再在数组中寻找。

实现1

public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (target - nums[i] == nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

分析
没错，就是和第一解法时间空间复杂度都是一样的😂。没事，我们可以优化一下的。

实现2

在实现一中，我们的瓶颈主要是在如何根据值去找到索引的问题上，所以这里我们使用Map去优化根据值去寻找位置的瓶颈

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析:
我们使用一个循环把数据与位置建立索引，然后获取的时候直接从map中直接获取，这样就可以避免了两个嵌套的循环了，是的时间复杂度为O(n) ,空间复杂度为O(1).

note: 在算法中，我们不考虑map这些数据结构具体实现使用的时间

实现3

实现2中使用了两个循环，能不能把第一个循环也去掉呢？答案是可以的。一边循环，一边插入map，然后获取这个差值是否已经加入到map中。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析：
这个复杂度和实现2是一样的，时间为O(n),空间为O(n)，但细看还是有差别的，这个算法的实际上比实现2的快了1倍