【LeetCode刷题0001】-两数之和

柔光的暖阳◎ 2023-03-06 05:57 19阅读 0赞

> <table> 
>  <tbody> 
>   <tr> 
>    <td><strong>LeetCode编程题解2000道(持续更新！ )</strong></td> 
>    <td><strong><a href="https://libusi.blog.csdn.net/article/details/95221793" rel="nofollow">https://libusi.blog.csdn.net/article/details/95221793</a></strong></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>  
> 
>     题目:
>     
>     给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
>     
>     你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍
> 
> ### **1）暴力破解** ###
> 
>     注意问题:
>     数组中同一个元素不能使用两遍,所以不能和自己相加,不然数组{3,2,4},target = 6会返回{0,0}
>     所以需要先坐下判断,如果用值做判断,{3,3},target = 6不会返回{0,1},很明显是满足的
>     使用数组下标判断即可
>     时间复杂度：O(n2)
>     空间复杂度：O(1)
> 
>     public static int[] twoSum1(int[] nums, int target) {
>     
>             for (int i = 0; i < nums.length; i++) {
>                 for (int j = 0; j < nums.length; j++) {
>                     if (j != i && nums[j] == target - nums[i]) {
>                         return new int[]{i, j};
>                     }
>                 }
>             }
>             throw new IllegalArgumentException("no Two sum solution!");
>         }
> 
> ### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYnVzaTAwMQ_size_16_color_FFFFFF_t_70][]**2）利用Map的containsKe** ###
> 
>     利用Map的key不相同的特性
>     数组循环里判断map是否有当前数字
>     如果没有,则把差值做key,角标做value,比如第一个是2,则存(4,0),当数组遇到4的时候直接返回{get(4),当前值角标}
> 
>     private static int[] twoSum2(int[] nums, int target) {
>             Map<Integer, Integer> map = new HashMap<>();
>             for (int i = 0; i < nums.length; i++) {
>                 if (map.containsKey(nums[i])) {
>                     return new int[]{map.get(nums[i]), i};
>                 } else {
>                     map.put(target - nums[i], i);
>                 }
>             }
>             throw new IllegalArgumentException("no Two sum solution!");
>         }
> 
> ### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYnVzaTAwMQ_size_16_color_FFFFFF_t_70 1][] ###

> --------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYnVzaTAwMQ_size_16_color_FFFFFF_t_70]: /images/20230208/4e3df11e384c41a5855a87b8ae67376a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYnVzaTAwMQ_size_16_color_FFFFFF_t_70 1]: /images/20230208/16339b7b6cd549e3909a9b52fda93e0a.png