LeetCode刷题，记录学习

问题

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答

方法一：暴力法

遍历数组中每个元素x，查找是否存在一个值与target-x相等的目标元素

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length-1; 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)$
$$
\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}1 = \sum_{i=0}^{n-2}(n-1) - (i+1) + 1 \\\\
= \sum_{i=0}^{n-2}(n-i-1) = (n-1) + (n-2)+ … + 1 = \frac{n(n-1)}{2}
$$
空间复杂度： $O(1)$

方法二：哈希表

采用哈希表，通过以空间换时间，来保存数组中每个元素与其索引的对应关系。

在第一次迭代中，将每个元素的值和其索引添加到表中。
然后，在第二次迭代中，检查每个元素所对应的目标元素$target - nums[i]$是否存在于表中。
注意，该目标元素不能是 $nums[i]$ 本身

class Solution {
    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 temp = target - nums[i];
            if(map.containsKey(temp) && map.get(temp) != i) {
                return new int[] {i, map.get(temp)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：

时间复杂度： $O(n)$，哈希表将查找时间缩短到 $O(1)$。
空间复杂度： $O(n)$，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了$n$个元素。