Two Sum

发表于 | 更新于 | 分类于

最近一段时间准备开始刷leetcode的题目了，我会分享一些算法题，如果大家有任何问题或者意见建议，都可以发送邮件给我。

这道题是给定一个int数组，返回一个加起来等于指定数字的，两个数字组成的索引数组。
可以假定每个输入都有一个结果，且你不可以用同一个数字两次进行相加。
示例
给定 nums = [2, 7, 11, 15], target = 9,
由于 nums[0] + nums[1] = 2 + 7 = 9,
所以返回 [0, 1].

方法一：暴力循环

最简单的方法，循环整个数组，获取元素x然后再遍历数组得到另外一个元素y等于target-x。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    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 (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

方法二：两步hash table

思路：使用一个hash table去存储int数组的值和索引，hash table的key是值，value是对应的索引。
步骤：
第一步先遍历数组得到这个hash table
第二步遍历数组，然后检查是否target-x存在于hash table的key中。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    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 (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

方法三：一步hash table

思路：hash table可以不用最开始的时候遍历数组得到，可以在遍历时候把插值到hash table的动作也完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    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");
    }
}

复杂度分析：
时间复杂度：$O(n)$
空间复杂度：$O(n)$