leetcode01

1 两数之和

经典力扣第一题，求两数之和。给定一个整形数组，并给定一个target值，判断在数组中是否存在两个元素，它们的和等于给定的target值，并返回这两个数组的下标。

例：

1 2	输入: nums = [2, 7, 11, 15], target = 9 输出: indexes = [0, 1]

#### 1.1 暴力解法

用双重循环来遍历数组，取出一个数组元素，并与后面的每一个元素进行相加然后比较是否与target相等，如果相等则直接返回当前元素的下标，否则返回null。看代码：

class Solution {
    public int[] twoSum(int target, int[] nums) {
        //存放返回数组的下标
        int[] indexes = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    indexes[0] = i;
                    indexes[1] = j;
                    return indexes;
                }
            }
        }
        
        return null;
    }
}

上面算法可以达到题目要求，但是时间复杂度比较高，两层循环，时间复杂度为O(n^2)。可以优化

1.2 使用map

使用一个map来存放数据，for循环遍历数组，并判断当前遍历的元素，target-当前元素的值，是否存在在map中，如果存在，说明找到了两个数相加 == target。如果不存在，就放入map中

class Solution {
    public int[] twoSum(int target, int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i];
            if (map.containsKey(num)) {
                return new int[] {map.get(num), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
    
}

通过一个map就可以做到，从而时间复杂度降低到O（n）。