Leetcode-problem1

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:

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

1.暴力法

遍历每个元素，查找符合结果的值

public int[] twoSum(int[] nums, int 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 number");    //非法参数异常，对于输入没有指定的解
    ｝
｝

复杂度分析：

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

2.哈希表

将一次遍历转换为哈希表（HashMap）

public class Solution2 {
    public int[] twoSum(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length;i++){                             //定义哈希表，以元素的值为key，元素的位置为value
            map.put(nums[i], i);
        }
        for(int i =0 ;i<nums.length;i++){                              //遍历数组，对于每一个值在哈希表中寻找对应的值使之相加为target目标值
            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");              //非法参数异常，对于输入没有指定的解
    }

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

 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);
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(nums[i]) != i) {
                return new int[] { nums[i], complement };
            }
        }

        throw new IllegalArgumentException("No two sum");            //非法参数异常，对于输入没有指定的解
    }

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

当数组的长度超过一定的范围时，使用HashMap的思想会更好