Leetcode算法题逐一击破—No.001

末蓝、 2023-01-02 10:25 75阅读 0赞

## \[每日一道算法题\] ##

# 题号：001
    # 题名：两数之和
    # 难度：简单

**题目描述：**

*  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 **和为目标值** 的那 **两个** 整数，并返回它们的数组下标。
    
     *  你可以假设每种输入只会对应 **一个** 答案。但是，数组中同一个元素 **不能使用两遍**。
     *  你可以按 **任意顺序** 返回答案。

**解题思路(一)：**

*  双层循环遍历数组，在数组中寻找target - nums\[i\]，找到时输出两数的下标

**解题代码：**

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            int[] a = new int[2];
            int oth;
            for(int i = 0 ; i < nums.length ; i++){ 
                 oth = target - nums[i];
                 for(int j = i + 1 ;j < nums.length ; j++){ 
                     if(oth == nums[j]){ 
                         a[0] = i;
                         a[1] = j;       
                     }
                 }
            }
            return a;
        }
    }

![在这里插入图片描述][20210105152312660.png]

**解题思路(二)：**

*  通过哈希表，key为数组nums中的元素值，value则为数组元素下标，将nums中的元素存到HashMap中
 *  利用HashMap的containsKey方法来找到指定元素，然后获取对应下标
 *  如果不存在，则抛出异常

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

![在这里插入图片描述][20210105152331624.png]

**总结**

*  思路一：双层循环查找，时间复杂度*O*(*N*2)，空间复杂度*O*(1).
 *  思路二：哈希表查找，时间复杂度*O*(N)，空间复杂度O(N).

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/two-sum

[20210105152312660.png]: /images/20221119/ecad34ac50314e0f8d75c90cd511f7a0.png
[20210105152331624.png]: /images/20221119/888988ea3c5f48c0ae93dec558c09876.png