1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例

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

解答方法

暴力法

 暴力法实现比较简单, 遍历数组中的每一个元素, 并且查找数组中是否存在一个与target-值相等的数.正所谓力大砖飞,这个世界上就没有暴力法解决不了的事, 如果有,那就是不够暴力.

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表的方法

 借助Hash表,遍历数组,将元素和它的索引记录在Hash表中,并且在遍历的同时检查是否存在和当前元素对应的目标元素,如果存在.那么返回结果.

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

时间复杂度与空间复杂度分析

• 时间复杂度 : O(n), 只遍历了一次含有n个元素的数组, 时间复杂度取决于数组长度. 故为O(n).
• 空间复杂度 : O(n), 使用了Hash表来存放元素, 故空间复杂度为O(n).