两数之和 LeetCode 1.Two Sum

心已赠人 2022-03-11 10:10 122阅读 0赞

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
    
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            for (int i = 0; i < nums.length; i++) { 
                int complement = target - nums[i];
                for(int j = 0;j < i;j++){ 
                    if(nums[j] == complement)return new int[] {  i,j };
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

如图：设target为5  
![在这里插入图片描述][20190307200721717.png]  
当蓝色箭头在第一位置的时候，使用红色箭头从头遍历直到蓝色箭头处，验证蓝色箭头和红色箭头的值和是否为5，不为5，蓝色箭头右移一位。  
![在这里插入图片描述][20190307200942255.png]  
再次验证红色箭头从头遍历直到蓝色箭头处，验证蓝色箭头和红色箭头的值和是否为5，不为5，蓝色箭头右移一位。直至蓝色箭头右移到最后一处。  
![在这里插入图片描述][20190307201046696.png]  
红色箭头此次遍历到第二位发现3+2=5，得到答案。  
![在这里插入图片描述][20190307201303528.png]  
  以上做法将数列遍历的两次，能不能再优化一下，如果用java的话可以使用HashMap，见下：

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

第二种方法和第一种方法区别就在于第一种是我们自己去遍历查找符合条件的数的位置，第二种是使用HashMap的containsKey(Object key)方法。hash查找效率比遍历查找效率要高。

[20190307200721717.png]: /images/20220311/6238fe839bbf4707b980b1059651bc8c.png
[20190307200942255.png]: /images/20220311/8719364fa35040a6b70a10450d4b2d5e.png
[20190307201046696.png]: /images/20220311/8e394cbad5d64061a864c857d7b8fe63.png
[20190307201303528.png]: /images/20220311/815d3c544af34cdc9a8c95ca249b9469.png