1.Two Sum

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.



编程语言:java


第一次尝试:就是普通的使用两个for循环,遍历寻找给出的数组中的数,计算两数之和,当有两个数字之和为目标数字时,就跳出循环并返回这两个数字的下标。

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

在网上看到,这种基本的方法虽然能解决问题,但是不够快捷,也不够逼格,看见有人使用hashMap来解决这个问题,小白没有学过hashmap,所以,借此机会,顺便学习一下。使用hashmap将原本算法的时间复杂度由O(N)降为O(1),key存放数值,value存放出现的位置,从前向后进行遍历,用目标值减去当前的值,看是否存在map中,若存在则取出相应的标号,退出。
Best Practice:

public int[] twoSum(int[] nums, int target) {
int[] answer = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i){
    map.put(nums[i], i);
}
for (int i = 0; i < nums.length; ++i){
    int b = target - nums[i];
      if (map.containsKey(b) && i != map.get(b))
          return new int[]{i, map.get(b)};
 }
 return answer;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容